LeetCode 115. 不同的子序列（DP）

示例 1：
输入：S = "rabbbit", T = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

示例 2：
输入：S = "babgbag", T = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。 
(上箭头符号 ^ 表示选取的字母)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

class Solution {
public:
    int numDistinct(string s, string t) {
        if(t=="") return 1;
        if(s.size() < t.size()) return 0;
        int m = s.size(), n = t.size(), i, j;
        vector<vector<long>> dp(m+1, vector<long>(n+1,0));
        for(i = 0; i <= m; ++i)
            dp[i][0] = 1;
        for(j = 1; j <= n; j++)//T字符
        {
        	for(i = 1; i <= m; i++)//S字符
        	{
        		if(s[i-1]==t[j-1])//相等时，相比下面不相等时，多了一种情况
        		//让 i, j, 匹配，前面的有多少种情况，dp[i-1][j-1]
        			dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
        		else//不相等时，相当于第i个字符没有用
        			dp[i][j] = dp[i-1][j];
        	}
        }
        return dp[m][n];
    }
};