📚115. Distinct Subsequences

"求S有多少个不同的子串与T相同"
count the number of distinct subsequence of T in S.

如果两个character相同，dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + dp[ i-1 ][ j ];
如果两个character不同，dp[ i ][ j ] = dp[ i-1 ][ j ];

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