Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

[Thoughts]:
看到String，首先应该想到的就是DP，想到DP就要开始想DP function。

res[i][j] =  number of distinct subsequences of T(0,j) in S(0,i).
If S.charAt(i) == T.charAt(j)   res[i][j] = res[i-1][j-1] + res[i-1][j].  otherwise res[i-1][j]. 
res[i-1][j-1] 表示结果集加上i对应j这位。 
res[i-1][j] 表示结果集不加i对应j这位， 那么（i，j）不能算S[i], 就只能等于（i-1，j）
1 2  3  4  5  6  7
r  a  b  b  b  i   t 
r  a  b  b  i   t     For Example: S[5]==T[4], res[5][4] = (rabb, rab) + (rabb，rabb）。

public class Solution {
    public int numDistinct(String S, String T) {
        int[][] res = new int[S.length()+1][T.length()+1];
        for(int i=0; i<S.length(); i++)
            res[i][0] = 1;
        for(int i=1; i<=S.length(); i++){
            for(int j=1; j<=T.length(); j++){
                res[i][j] = res[i-1][j] + (S.charAt(i-1) == T.charAt(j-1) ? res[i-1][j-1] : 0);
            }
        }
        return res[S.length()][T.length()];
    }
}

二维数组可以换成滚动数组。 但注意第二个for循环T要倒过来遍历，因为res[j-1]要用i-1那层的数据，正着循环j-1已被i层更新覆盖。

public class Solution {
    public int numDistinct(String S, String T) {
        int[] res = new int[T.length()+1];
        res[0] = 1;
        
        for(int i=1;i<=S.length();i++){
            for(int j=T.length();j>=1;j--){//note: 从后往前
                res[j] += S.charAt(i-1)==T.charAt(j-1) ? res[j-1] : 0;
            }
        }
        return res[T.length()];
    }
}