"求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];
}
}
