【dp】leetcode 115. Distinct Subsequences
【dp】leetcode 115. Distinct Subsequences。
dp 与公共子串匹配的算法思想类似
当当前字符s与t匹配时，次数dp[i][j] 可以采用两种方式进行计算，1）s[j]与t[i]匹配 为 dp[i-1][j-1] 2) 不考虑新加入的字符 s[j] ，为dp[i][j-1]. 两种情况相加就可以得到了
public class Solution {
public int numDistinct(String s, String t) {
int[][] dp = new int[t.length()+1][s.length()+1];
for(int j=0;j<=s.length();j++){
dp[0][j] = 1;
}
for(int i=1;i<=t.length();i++){
for(int j=1;j<=s.length();j++){
if(s.charAt(j-1)==t.charAt(i-1)){
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
}else{
dp[i][j] = dp[i][j-1];
}
}
}
return dp[t.length()][s.length()];
}
}
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻