y***n
发帖数: 1594 | 1 code 和简洁，不是很想的清楚。
int numDistinct(string S, string T) {
vector 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
f[j]+=(S[i]==T[j])*f[j+1];
}
}
return f[0];
} |
J****3
发帖数: 427 | 2 DP 方程 assume dp[i][j] means number of distinct subsequence number of S[0,i
] and T[0,j]
then for each character, two cases: 1. S[i] != T[j]: dp[i][j] = dp[i-1][j].
2. S[i] == T[j]: dp[i][j] = dp[i-1][j] + dp[i-1][j-1].
我们可以依据方程写出DP， 普通是2维，lz给的是一维滚动数组， 遍历方向相反可以
防止重复计算 |
y***n
发帖数: 1594 | |
J****3
发帖数: 427 | 4 比较S[i] 和 T[j], 如果这俩字符不一样， 我们肯定是从剩下的 S[i-1] sequence里
去找 T字符串， 如果这俩字符一样的话，
一种情况是S和T都-1，还有是只有S -1 继续从S-1里找T
【在 y***n 的大作中提到】
: 能够解释一下这两个case 吗？
|
y***n
发帖数: 1594 | |
h******6
发帖数: 2697 | 6 先把f改成2维的写一个code 然后再缩减为一维的就清晰多了 |
x*******8
发帖数: 145 | 7
,i
.
解释的不错啊，被你这么一说，我也清楚多了，那这种普通2维是不是都可以通过相反
滚动转化成一维
【在 J****3 的大作中提到】
: DP 方程 assume dp[i][j] means number of distinct subsequence number of S[0,i
: ] and T[0,j]
: then for each character, two cases: 1. S[i] != T[j]: dp[i][j] = dp[i-1][j].
: 2. S[i] == T[j]: dp[i][j] = dp[i-1][j] + dp[i-1][j-1].
: 我们可以依据方程写出DP， 普通是2维，lz给的是一维滚动数组， 遍历方向相反可以
: 防止重复计算
|
