題目描述

給定一個字符串 S 和一個字符串 T，計算在 S 的子序列中 T 出現的個數。
一個字符串的一個子序列是指，通過刪除一些（也可以不刪除）字符且不干擾剩余字符相對位置所組成的新字符串。（例如，"ACE" 是 "ABCDE" 的一個子序列，而 "AEC" 不是）

題目數據保證答案符合 32 位帶符號整數范圍。

示例 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
    ^^^

解題思路

如果s的最后一個字符與t的最后一個字符不相同，那么就只能從s第0到第n-2字符與t去比較，這樣就有dp[m-1][n]種方式。
如果s的最后一個字符與t的最后一個字符相同，那么除上面那么種外，還可以有dp[m-1][n-1]種。

    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=0;i<=m;i++)
            dp[i][0] = 1;
        
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j] = dp[i-1][j];
                if(s[i-1]==t[j-1])
                    dp[i][j] += dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }