public class Subsequence {
    public static  int numDistinct(String s, String t) {
        //二维数组
        /*
        int n=s.length();
        int m=t.length();
        int[][] dp=new int[n+1][m+1];//定义二维数组存储s的前i个字符中（子序列）出现t的前j个字符的个数，注意子序列可以是s通过删除得到的也可以不删除得到
        //初始化
        for(int i=0;i<=n;i++) dp[i][0]=1;//s的前i个子串中找到空串的个数都是1，因为可以通过删除的到空串
        for(int j=1;j<=m;j++) dp[0][j]=0;//s的空串中含有t的前j个字符的个数为0
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                //如果s的第i个字符与t的第j个字符相等，那么分两种情况：
                1、用第j个字符去匹配，那么就只计算s中前i-1个和t中前j-1个相等的个数
                2、不用第j个字符去匹配，那么就计算s中前i-1个跟t中前j个相等的个数
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j];//如果不相等，那么就是s中前i-1个和t中前j个相等的个数
                }
            }
        }
        return dp[n][m];

         */
        //一维数组优化，我们可以发现dp[i][j]只跟dp[i-1]的元素有关，所以只需要利用一维数组存储之前的值即可
         int n=s.length();
        int m=t.length();
        int[] dp=new int[m+1];//定义二维数组存储s的前i个字符中（子序列）出现t的前j个字符的个数，注意子序列可以是s通过删除得到的也可以不删除得到
        dp[0]=1;//对应dp[0][0]
        for(int j=1;j<=m;j++) dp[j]=0;//初始化，没有i,相当于空串中有t中前j个字符的个数，对应dp[0][j]=0;
        for(int i=1;i<=n;i++){
            for(int j=m;j>0;j--){
                //由于当前的值需要用到上一轮i的j-1的值，是旧的值，但是如果j从小到大的话，那么j-1的值就会被更新为这一轮的j-1的值，会覆盖上一轮的j-1的值，
                // 但是我们需要用到的j-1的值是上一轮i-1的而不是这一轮的，所以如果要用旧的j-1的值的话，那么就要让j从大到小就可以实现j-1的值是上一轮i-1的，没有更新的值
                if(s.charAt(i-1)==t.charAt(j-1)){
                    //当s的第i个字符跟t的第j个字符相等时，那么就是上一轮的dp[j-1]的值和dp[j]的值相加，就看成是跟二维数组的两种情况：当利用t[j-1]和不利用t[j-1]去匹配的情况
                    dp[j]=dp[j-1]+dp[j];
                }
            }
        }
        return dp[m];
    }
}