leetcode115-不同的子序列

不同的子序列

• dp

维护一个二维dp数组，分别表示s[0:i]和t[0:j]的分配种类。
如果j等于0，由于模式串没有进行匹配，那么对于所有的原串来说，都只有一种匹配方式，所以需要赋值1。
然后进行遍历，如果s[i]和t[j]相同，那么有两种选择，匹配或者不匹配，dp[i][j] = dp[i-1][j-1] + dp[i][j-1]。如果不同，那么只能选择不匹配，dp[i][j] = dp[i][j-1]
最后返回dp[m][n]即可

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length(), dp[][] = new int[m+1][n+1];
        for(int i = 0; i <= m; i++) dp[i][0] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s.charAt(i-1) == t.charAt(j-1))  dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[m][n];
    }
}