总结:字符串子序列dp问题

问题一:统计字符串A中有多少个子序列 = 字符串 B

令dp(i , j) 为字符串A前i位，有多少个子序列 = B的前j位.

假设 B = XXLL

那么dp[i][1] 代表 子序列 "X"的个数

dp[i][2] 代表 子序列 "XX"的个数

dp[i][3] 代表 子序列 "XXL"的个数

dp[i][4] 代表 子序列 "XXLL"的个数

递推也很显然: XXLL 形成的条件是:  第i位为"L"且 1 ~ i - 1 中存在子序列 XXL

dp[i][j] = dp[i - 1][j]  //  当 A[i] != B[j]

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]  //  当 A[i] = B[j]

问题二:你可以修改字符，使得字符串A中不存在子序列 = 字符串 B 的最小修改次数.

其实跟上面意思一样，这里就是求一个最优化。

利用自顶向下的方式，递归的去解决这个问题。

令dp[i][j]为A字符串前i个，使得不存在前j的B字符串的最少修改次数。

dp[i][j] = dp[i - 1][j]  //  当 A[i] != B[j]

dp[i][j] = min(dp[i - 1][j - 1] + 1 , dp[i - 1][j - 1] ) //  当 A[i] = B[j] ， 就是改或不改。

改的话，就往前。不改，那么就要求前i - 1 个数不存在 前j个B字符串。

还要注意到，给定的i， dp[i] 数组是非上升的。 因为限制条件越严格.

问题三:统计字符串中有多少个不同的字符串子序列

如果没有本质不同的限制 ，那么转移为 dp(i , j ) = dp(i - 1 , j) + dp(i - 1, j - 1).

有了本质不同。考虑当前一个以字母a结尾的长度为j的字符串集合.

....a

....a

.....a   

那么当现在又遇到一个字母a，求它的长度为j的子序列的个数时，重复的部分就是之前以字母a结尾的长度为j的字符串个数   容斥掉这个部分即可。

答案就是 dp[n][1] + ... + dp[n][n]