力扣

思路 💥

设 dp[i][j] 代表: 在 s[:i] 的子序列中 t[:j] 出现的个数。

则有以下递推公式：

$$ dp[i][j] = \begin{cases} dp[i-1][j-1] + dp[i-1][j] , \ s[i] == t[j] \\ dp[i-1][j] , \ \text{Other} \end{cases} \tag{1} $$

Code 🐘

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<uint64_t>> dp(m+1,vector<uint64_t>(n+1,0));
        for(int i = 0; i <= m; i++) dp[i][0] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; 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[m][n];
    }
};

复杂度分析 🥇

优化版本

由式（1）可以看出 dp[i][j] 只与 dp[i-1][j-1] 和 dp[i-1][j] 相关，则可以将数组空间进行压缩:

$$ dp[j] = \begin{cases} dp[j-1] + [j] , \ s[i] == t[j] \\ dp[j] , \ \text{Other} \end{cases} \tag{2} $$

同时代码优化为:

class Solution {
public:
    int numDistinct(string s, string t) {
       
        int m = s.size(), n = t.size();
        vector<uint64_t> dp(n+1,0);
        // 注意此处的初始化，其本质为dp[i][j] 数组中的第一行
        dp[0] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = n; j >= 1; j--){
                if(s[i-1] == t[j-1]){
                    dp[j] += dp[j-1];
                    // dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                }
            }
        }
        return dp[n];
    }
};

此时的复杂度分析为