public class _115 {
    static class Solution1{
        Integer[][] dp;
        public int numDistinct(String s, String t) {
            dp = new Integer[s.length()][t.length()];
            return dfs(s,t,0,0);
        }

        public int dfs(String s,String t,int i,int j){
            if(j==t.length())return 1;
            if(i == s.length()) return 0;
            if(dp[i][j] != null) return dp[i][j];
            int res = 0;
            if(s.charAt(i) == t.charAt(j)){
                res += dfs(s,t,i+1,j+1);
            }
            res += dfs(s,t,i+1,j);
            return dp[i][j] = res;
        }
    }

    static class Solution2{
        public int numDistinct(String s, String t) {
            //s[x,s.length()-1], t[y,t.length-1]
            //dp[x][y] 分别代表[y,t.length()-1]在 [x,s.length()-1]中作为子串的出现次数
            int[][] dp = new int[s.length()+1][t.length()+1];
            for(int i = 0;i < dp.length;i++){
                dp[i][t.length()] = 1;
            }
            char[] sc = s.toCharArray();
            char[] tc = t.toCharArray();
            for(int y = tc.length-1;y >= 0;y--){
                for(int x = sc.length-1;x >=0;x--){
                    dp[x][y] = dp[x+1][y] + (sc[x] == tc[y] ? dp[x+1][y+1] : 0 );
                }
            }
            return dp[0][0];
        }
    }
}