public class Solution {
    public int numDistinct(String s, String t) {
        int length = s.length();
        int width = t.length();
        if(length==0||width==0) return 0;
        int[][] dp = new int[length][width];
        int count = 0;
        for(int i = 0; i < length; i++)
        {
            if(s.charAt(i)==t.charAt(0)) count++;
            dp[i][0]=count;
        }
        for(int i = 1; i < length; i++)
        {
            for(int j = 1; j < width; 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[length-1][width-1];
    }
}