LeetCode 115. 不同的子序列

LeetCode 115. 不同的子序列

思路：

以s[i]是否被选择做划分，如果不选择，f[i][j] = f[i-1][j],如果s[i]被选择，则 f[i][j] = f[i-1][j] + f[i-1][j-1](两种情况的和)。

代码：

class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.size(),m=t.size();
        vector<vector<unsigned long long>>res(n + 1 , vector<unsigned long long> (m + 1));
        s = ' ' + s,t= ' ' + t;
        for(int i=0;i<=n;i++) res[i][0] = 1;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                res[i][j] = res[i-1][j];
                if(s[i] == t[j]) res[i][j] += res[i-1][j-1];
            }
        }
        return res[n][m];
    }
};