給出字符串S和字符串T，計算S的不同的子序列中T出現(xiàn)的個數(shù)。

子序列字符串是原始字符串通過刪除一些(或零個)產(chǎn)生的一個新的字符串，并且對剩下的字符的相對位置沒有影響。(比如，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。
樣例
給出S = "rabbbit", T = "rabbit"

返回 3

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 tLength = T.size();
        int sLength = S.size();
        vector<vector<int>>dp(tLength+1,vector<int>(sLength+1,0)) ;
        for(int i = 0;i < sLength+1;i++) {
            dp[0][i] = 1;
        }
        for(int i = 1; i<tLength+1;i++){
            for(int j=1; j<sLength+1;j++) {
                //之前在這里寫成S[j-1] == T[i-1]導(dǎo)致花了很多時間，動態(tài)規(guī)劃的狀態(tài)方程和操作字符安串的下標(biāo)一般是不對稱的?。?！
                if(S[j-1] == T[i-1]) {
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
                } else {
                    dp[i][j] = dp[i][j-1];
                }
              //  dp[i][j] = ((S[j] == T[i])?(dp[i-1][j-1]):0) + dp[i][j-1];
            }
        }
        return dp[tLength][sLength];
    }
};

參考LeetCode
解釋
dp[i][j] = dp[i][j-1] + dp[i-1][j-1];

dp[i][j] 為字符串S(0,i-1)到T(0,j-1)的S的子序列中T出現(xiàn)的個數(shù)
當(dāng)S[j-1] == T[i-1]

• dp[i][j-1]表示前面符合條件的子串
• dp[i-1][j-1]表示加上字符s[i-1]后符合條件個數(shù)

動態(tài)規(guī)劃的狀態(tài)方程和操作字符安串的下標(biāo)一般是不對稱的?。?！