不同的子序列DP解释
来自LeetCode
给定一个字符串S和一个字符串T，计算S中不同子序列的个数。
字符串的子序列是由原始字符串形成的新字符串，通过删除字符中的一些（可以不是）而不干扰其余字符的相对位置。 （即“ACE”是“ABCDE”的子序列，而“AEC”不是）。
这里是一个例子：S =“兔子”，T =“兔子”
返回3。
我看到一个很好的DP解决方案，但是，我很难理解它，任何人都可以解释这个DP如何工作？
int numDistinct(string S, string T) {
vector<int> f(T.size()+1);
//set the last size to 1.
f[T.size()]=1;
for(int i=S.size()-1; i>=0; --i){
for(int j=0; j<T.size(); ++j){
f[j]+=(S[i]==T[j])*f[j+1];
printf("%dt", f[j] );
}
cout<<"n";
}
return f[0];
}
首先，尝试自己解决这个问题，以提出一个天真的实现：
假设S.length = m和T.length = n 。 我们写S{i}作为从i开始的S的子串。 例如，如果S = "abcde" ， S{0} = "abcde" ， S{4} = "e" ， S{5} = "" 。 我们对T使用类似的定义。
令N[i][j]为S{i}和T{j}的不同子序列。 我们对N[0][0]感兴趣（因为它们都是完整的字符串）。
有两种简单的情况：对于任何i ， N[i][n] ，对于j<n ， N[m][j] 。 ""在一些字符串S中有多少个子序列？ 正确1. ""多少个T ？ 只有0。
现在，给定一些任意的i和j ，我们需要找到一个递归公式。 有两种情况。
如果S[i] != T[j] ，我们知道N[i][j] = N[i+1][j] （我希望你自己可以证明这一点，我打算解释上面的神秘算法详细地说，不是这个天真的版本）。
如果S[i] = T[j] ，我们有一个选择。 我们可以'匹配'这些字符并继续与S和T的下一个字符，或者我们可以忽略匹配（就像在S[i] != T[j] ）。 既然我们有两种选择，我们需要在那里增加计数： N[i][j] = N[i+1][j] + N[i+1][j+1] 。
为了使用动态编程来查找N[0][0] ，我们需要填充N表。 我们首先需要设置表格的边界：
N[m][j] = 0, for 0 <= j < n
N[i][n] = 1, for 0 <= i <= m
因为在递归关系的依赖关系，我们可以填写表循环的其余部分i向后和j转发：
for (int i = m-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (S[i] == T[j]) {
N[i][j] = N[i+1][j] + N[i+1][j+1];
} else {
N[i][j] = N[i+1][j];
}
}
}
我们现在可以使用算法的最重要的技巧：我们可以使用一个一维数组f ，并在外部循环中使用不变量： f = N[i+1]; 这是可能的，因为桌子被填满了。 如果我们将此应用于我的算法，则会得出：
f[j] = 0, for 0 <= j < n
f[n] = 1
for (int i = m-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (S[i] == T[j]) {
f[j] = f[j] + f[j+1];
} else {
f[j] = f[j];
}
}
}
我们差不多就是你给的算法。 首先，我们不需要初始化f[j] = 0 。 其次，我们不需要赋值类型f[j] = f[j] 。
由于这是C++代码，我们可以重写代码片段
if (S[i] == T[j]) {
f[j] += f[j+1];
}
至
f[j] += (S[i] == T[j]) * f[j+1];
就这样。 这产生了算法：
f[n] = 1
for (int i = m-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
f[j] += (S[i] == T[j]) * f[j+1];
}
}
我认为答案很好，但有些东西可能不正确。
我认为我们应该通过i和j向后迭代。 然后我们将数组N为数组f ，我们向前循环j以便不重叠最后得到的结果。
for (int i = m-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (S[i] == T[j]) {
N[i][j] = N[i+1][j] + N[i+1][j+1];
} else {
N[i][j] = N[i+1][j];
}
}
}