distinct-subsequences

力扣

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

思路 💥

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

则有以下递推公式：

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];
    }
};

复杂度分析 🥇

时间复杂度	空间复杂度
O(NM)	O(NM)

优化版本

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

同时代码优化为:

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];
    }
};

此时的复杂度分析为

时间复杂度	空间复杂度
O(N)	O(N)