https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

1.本题在上一个题的基础上理解起来就容易多了，上一题是在字符串s里找到有没有字符串t所以我们定义的dp数组就是在dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度 所以我们判断有几个数符合不符合的通过状态转移找到上一个子结果的值，本题是在字符串s里找到有几个字符串t，所以dp数组的定义就是dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。当两数相等的时候我们考虑第一种情况就是使用这个s[i – 1]的数这样就是dp[i][j] = dp[i - 1][j - 1]同时我们也考虑不使用这个值s[i - 1]这样可能在这个值之前也有符合题意的结果。两数不相等就把s[i -1]删了就是不考虑这个树，返回上一个子结果。

CPP

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