Redian新闻
>
急:请推荐费城home inspector
avatar
急:请推荐费城home inspector# Living
y*n
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; jf[j]+=(S[i]==T[j])*f[j+1];
}
}
return f[0];
}
avatar
S*t
2
必须要下周完成home inspection,请推荐费城比较好的home inspector.
多谢!
avatar
J*3
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给的是一维滚动数组, 遍历方向相反可以
防止重复计算
avatar
B*y
4
去Angie's list花钱注个号,找个Review好的Inspector就可以了。

【在 S*****t 的大作中提到】
: 必须要下周完成home inspection,请推荐费城比较好的home inspector.
: 多谢!

avatar
y*n
5
能够解释一下这两个case 吗?
avatar
J*3
6
比较S[i] 和 T[j], 如果这俩字符不一样, 我们肯定是从剩下的 S[i-1] sequence里
去找 T字符串, 如果这俩字符一样的话,
一种情况是S和T都-1,还有是只有S -1 继续从S-1里找T

【在 y***n 的大作中提到】
: 能够解释一下这两个case 吗?
avatar
y*n
7
谢谢,想通了。
avatar
h*6
8
先把f改成2维的写一个code 然后再缩减为一维的就清晰多了
avatar
x*8
9

,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给的是一维滚动数组, 遍历方向相反可以
: 防止重复计算

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。