1 // 从下至上
2 class Solution {
3 public int numDistinct(String s, String t) {
4 if(s.length()<t.length()){
5 return 0;
6 }
7 // dp[i][j] 表示是 t[j:] 作为 s[i:] 子序列的个数
8 int[][] dp = new int[s.length()+1][t.length()+1];
9 for(int i = 0;i<dp.length;i++){
10 dp[i][t.length()] = 1;
11 }
12 for(int i = s.length()-1;i>=0;i--){
13 char ch = s.charAt(i);
14 for(int j = t.length()-1;j>=0;j--){
15 if(ch == t.charAt(j)){
16 // 记录 s[i] 与 t[j] 匹配与不匹配时，所有子序列次数
17 dp[i][j] = dp[i+1][j+1] + dp[i+1][j];
18 }else{
19 // 记录 s[i] 与 t[j] 不匹配时，所有子序列次数
20 dp[i][j] = dp[i+1][j];
21 }
22 }
23 }
24 return dp[0][0];
25
26 }
27 }