115. Distinct Subsequences

DP

class Solution {
    public int numDistinct(String s, String t) {
        //dp[i][j] i ist the substring length of s, j is the substring length of t
        // 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];
        
        // if t is empty, the only substring for s is an empty string
        // dp[i][0] =1; 
        // dp[0][j] = 0;
        
        // memory improvement: memo[t.length()+1] to save the result of previous row
        
        int[] memo = new int[t.length()];
        int preValue=0;
        for (int i=0; i<s.length(); i++){
            for(int j=0; j<t.length(); j++){
                if(j==0) preValue=1;
                int temp = memo[j];
                if(s.charAt(i)==t.charAt(j)) memo[j]=preValue+memo[j];
                preValue=temp;
            }
        }
        return memo[t.length()-1];
    }
}