115.不同的子序列

扇贝力扣

最后一个测试案例答案是-1

递推公式想不清楚啊 啊嗷嗷啊

class Solution {
public:
    int numDistinct(string s, string t) {
        // dp[i][j] = s[0:i-1]的子序列中t[0:j-1]出现的次数
        vector<vector<unsigned long long>>dp(s.size()+1,vector<unsigned long long>(t.size()+1,0));
        dp[0][0]=1;
        // for(int i=1;i<t.size()+1;i++)dp[0][i]=1;
        for(int j=1;j<s.size()+1;j++)dp[j][0]=1;
        // dp[i][j]+=dp[i][j-1]
        // if(s[i-1]==t[j-1])dp[i][j]+=dp[i-1][j-1]
        for(int i=1;i<s.size()+1;i++)
        for(int j=1;j<t.size()+1;j++){
            if(s[i-1]==t[j-1])
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            else
            dp[i][j]=dp[i-1][j];
        }
        return int(dp[s.size()][t.size()]);
    }
};