package String;

/**

* 动态规划

* 当T的长度大于S的长度时，S的子序列一定没有T，直接返回0

* dp[i][j]：表示S[i:]的子序列中T[j:]的个数

* dp[i][j]

* s[i]=[j]有两种选择，可以选择匹配也可以不选择匹配 dp[i+1][j+1]+dp[i+1][j]

* s[i]!=[j] dp[i+1][j]

*/

public class DistinctSubsequences_115 {

public int numDistinct(String s, String t) {

int m=s.length(),n=t.length();

if(n>m) return 0;

int[][] dp=new int[m+1][n+1];

//当j为n时，T为空串，是S的子序列，初始化为1，当i为m时，S是空串，初始化为0

for(int i=0;i<=m;i++){

dp[i][n]=1;

}

for(int i=m-1;i>=0;i--){

for(int j=n-1;j>=0;j--){

if(s.charAt(i)==t.charAt(j)){

dp[i][j]=dp[i+1][j+1]+dp[i+1][j];

}else{

dp[i][j]=dp[i+1][j];

}

}

}

return dp[0][0];

}

public static void main(String[] args) {

int i = new DistinctSubsequences_115().numDistinct("rabbbit", "rabbit");

System.out.println(i);

}

}