【LeetCode】Distinct Subsequences

DP.
假设dp[i][j]为T[j:end]作为子序列在S[i:end]中出现的次数，则有以下关系式
dp[i][j]=dp[i+1][j]+((T[j]==S[i])?1:0)*dp[i+1][j+1];
意思就是，T[j:end]作为子序列在S[i:end]中出现的次数，等于T[j]==S[i]时T[j+1:end]作为子串在S[i+1:end]中出现的次数，加上T[j:end]作为子串在S[i+1:end]中出现的次数。

class Solution {
public:
    int numDistinct(string S, string T) {
        if(T.length()>S.length()) return 0;
        vector<vector<int>> dp(S.length()+1,vector<int>(T.length()+1,0));
        for(int i=0;i<=S.length();i++) dp[i][T.length()]=1;
        for(int i=S.length()-1;i>=0;i--)
        {
            for(int j=T.length()-1;j>=0;j--)
            {
                dp[i][j]=dp[i+1][j]+((T[j]==S[i])?1:0)*dp[i+1][j+1];
            }
        }
        return dp[0][0];
    }
};