DP

状态表示：f[i][j]表示s[1 - i]的所有和t[1 - j]相等的子序列 的数量。

状态转移分析：

注意初始化：t为空时候,s的所有字符都不能选，则数量为1

$ 时间复杂度O(NM)$

参考文献

lc究极班

AC代码

class Solution {
public:
    typedef long long LL;

    int numDistinct(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<LL>> f(n + 1 ,vector<LL> (m + 1, 0));
        s = ' ' + s, t = ' ' + t; 
        //初始化,t为0个字符，s所有的字符删除才能匹配
        for (int i = 0 ; i <= n ; i ++)
            f[i][0] = 1;
        //DP
        for (int i = 1 ; i <= n ; i ++){
            for (int j = 1 ; j <= m ; j ++){
                if (s[i] == t[j]) f[i][j] += f[i - 1][j - 1];
                f[i][j] += f[i - 1][j];
            }
        }
        return f[n][m];

    }
};