Distinct Subsequence

题目：

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).

Example: Given S = "rabbbit", T = "rabbit", return 3.

分析：

这道题目的思维方式非常怪异

当S[i - 1] == T[i - 1]的时候，有两部分，

首先f[i - 1][j]指的是虽然相等，我也不用他们俩匹配，
用之前S中的[i - 1]个去匹配T的[j]个； 

f[i- 1][j - 1]指的是，既然相等，我们用两个新元素匹配，
这种情况的unique序列个数是用S的[i - 1]去匹配T的[j - 1]这么多种。

解法：

class Solution {
public:    
    /**
     * @param S, T: Two string.
     * @return: Count the number of distinct subsequences
     */
    int numDistinct(string &S, string &T) {
        // write your code here

        int m = S.size();
        int n = T.size();
        if (m == 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }

        vector<vector<int> > f(m + 1, vector<int>(n + 1, 0) );
        for (int i = 0; i <= m; i++) {
            f[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (S[i - 1] == T[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
                } else {
                    f[i][j] = f[i - 1][j];
                }
            }
        }

        return f[m][n];
    } 
};