115. 不同的子序列 (opens new window)

1.动规+长度继承

分析：本题与LCS最大的区别在于，字符串s中选择的子序列可以是连续的，而匹配串t在进行选择和匹配时必须是连续的。

更新时t串不能拆分，因此如果字符t[i]等于s[j]，那么t[0，i]的构成可以分成两种情况：

• 如果使用s串的第j个字符来组建t串，那么能够形成的子序列个数为dp[i][j]=dp[i-1][j-1]
• 如果不用当前s串第j个字符来组建t串，那么s[0，j-1]中能够组建t串的子序列个数需要继承"前一个s串"计算得到的长度，dp[i][j]=dp[i][j-1]

根据加法原理，两种情况的子序列个数相加作为当前的结果。

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp=new int[t.length()+1][s.length()+1];
        for(int i=0;i<=s.length();i++) dp[0][i]=1;
        for(int i=1;i<=t.length();i++){
            for(int j=1;j<=s.length();j++){
                if(t.charAt(i-1)==s.charAt(j-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()];
    }
}