Given a string S and a string T, count the number of distinct subsequences of T in S.
A
subsequence of a string is a new string which is formed from the original string
by deleting some (can be none) of the characters without disturbing the relative
positions of the remaining characters. (ie, "ACE" is a
subsequence
of "ABCDE" while "AEC" is
not).
Here is
an example:
S = "rabbbit", T = "rabbit"
Return 3.
1 public class Solution { 2 public int numDistinct(String S, String T) { 3 int lenS = S.length(); 4 int lenT = T.length(); 5 if(lenS==0) return 0; 6 if(lenT==0) return 1; 7 int dp[][] = new int [lenS+1][lenT+1]; 8 for(int i=0;i<=lenS;i++){ 9 dp[i][0] = 1; 10 } 11 for(int i=0;i<=lenT;i++){ 12 dp[0][i] = 0; 13 } 14 for(int i=0;i<=lenS;i++){ 15 for(int j=0;j<=lenT;j++){ 16 if(S.charAt(i)==T.charAt(j)){ 17 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; 18 } 19 else{ 20 dp[i][j] = dp[i-1][j]; 21 } 22 } 23 } 24 return dp[lenS][lenT]; 25 } 26 }
原文：http://www.cnblogs.com/krunning/p/3552039.html
