package question;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question115 {
 public int numDistinct(String s, String t) {
 int m = s.length();
 int n = t.length();
 int[][] dp = new int[n+1][m+1];
 dp[0][0]=1;
 for (int i = 1; i < dp.length; i++) {
 for (int j = 1; j < dp[i].length; j++) {
 if (t.charAt(i-1)==s.charAt(j-1)) {
 for (int k = j-1; k >= 0; k--) {
 dp[i][j]+=dp[i-1][k];
 }
 }
 }
 }
 int res=0;
 for (int num : dp[n]) {
 res+=num;
 }
 return res;
 }
}