115. Distinct Subsequences

This problem can be seen as a special match problem (10. Regular Expression Matching, 44. Wildcard Matching, 1023. Camelcase Matching) Normally, a match problem is related to substring while this one is related to subsequence. Such problem can be solved in dp. Here, we a two dimension array sum[i][j] to denote the number of subsequence of s[0, i] that can match t[0, j]:

1. Apparently, if j == 0, then there must be one subsequence, i.e., empty string to match it.
2. If s[i] == t[j], then sum[i][j] = sum[i - 1][j - 1] + sum[i - 1][j]
3. Otherwiese, sum[i][j] = sum[i - 1][j].

public int numDistinct(String s, String t) {
    int sum[][] = new int[s.length() + 1][t.length() + 1];
    for(int i = 0; i <= s.length(); i++)
        sum[i][0] = 1;
    for(int i = 0; i < s.length(); i++) {
        for(int j = 0; j < t.length(); j++) {
            sum[i + 1][j + 1] = sum[i][j + 1];
            if( s.charAt(i) == t.charAt(j) )
                sum[i + 1][j + 1] += sum[i][j];
        }
    }
    return sum[s.length()][t.length()];
}