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:

1. dp[i][j] = 0, if(i == 0) or (j == 0)
2. dp[i][j] = dp[i-1][j-1] + 1, if(s[i] == t[j])
3. dp[i][j] = max{dp[i][j-1] , dp[i-1][j] } , if(s[i] != t[j])

Longest Common Substring:

與上面的類似，當str1[i] == str2[j]時，子序列長度veca[i][j] = veca[i - 1][j - 1] + 1；區(qū)別是當str1[i] ！= str2[j]時，veca[i][j]長度要為0，而不是max{veca[i - 1][j], veca[i][j - 1]}。