Distinct Subsequences 這道題的題意要仔細理解番官。位衩。http://blog.csdn.net/fightforyourdream/article/details/17346385?reload#comments
是說，從s[i]中刪除一些字母變換到t[j]琼讽，有幾種方法必峰。
如果s[i]!=t[j]，說明s[i]這一位的添加钻蹬，對變換到t[j]的方法數(shù)增加沒有幫助吼蚁，因為仍然要把s[i]刪掉(在原來的每種刪除方法的基礎(chǔ)上，同時把s[i]加上)问欠，才能從s變換到t[j]肝匆。那就把s[i]刪掉吧，
所以顺献，dp[i][j] = dp[i-1][j]旗国。
如果s[i]==t[j]，舉個例子注整，
s="aarab | bbit",
t = "arab | bit"
豎線后面的那個b分別是s中的i和t中的j位能曾，那么同時加上這兩個b的話度硝，變換的方法不但要包含豎線前面的兩種dp[i-1][j-1]（因為原來怎么變，現(xiàn)在還可以那么變寿冕，不用管后面）蕊程，還要包含把s[i]刪掉能匹配t[j]的情況dp[i-1][j]。
dp[i][j] = dp[i-1][j]+ dp[i-1][j-1].
public int numDistinct(String s, String t) {
if (s.length() == 0 || t.length() == 0) return 0;
int dp[][] = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i < s.length() + 1; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < s.length() + 1; i++)
for (int j = 1; j < t.length() + 1; j++) {
if (s.charAt(i - 1) != t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
return dp[s.length()][t.length()];
}
Longest Common Subsequence:
- dp[i][j] = 0, if(i == 0) or (j == 0)
- dp[i][j] = dp[i-1][j-1] + 1, if(s[i] == t[j])
- dp[i][j] = max{dp[i][j-1] , dp[i-1][j] } , if(s[i] != t[j])
Longest Common Substring:
與上面的類似蚂斤，當(dāng)str1[i] == str2[j]時存捺，子序列長度veca[i][j] = veca[i - 1][j - 1] + 1；區(qū)別是當(dāng)str1[i] 曙蒸！= str2[j]時捌治，veca[i][j]長度要為0，而不是max{veca[i - 1][j], veca[i][j - 1]}纽窟。
