leetcode 115 Distinct Subsequences

https://www.cnblogs.com/grandyang/p/4294105.html

不同的子序列：

动态规划，dp[i][j]代表s[0...i]中t[0...j]有的个数。写出矩阵，找规律。

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