力扣 115. 不同的子序列

时间：2024-04-09 19:49:49

题目来源：https://leetcode.cn/problems/distinct-subsequences/description/

C++题解：动态规划。

dp[i][j] 表示 t[0] ~ t[i-1] 在 s[0] ~ s[j-1] 中出现的个数。因为 t 短，所以把 t 放在外循环。

当 t[i-1] 不等于 s[j-1] 时，s[j] 长度+1，t[0]~t[i-1]出现的个数不会变，所以dp[i][j] = dp[i][j-1];

当 t[i-1]  等于 s[j-1] 时，如果是s[0]，那么dp[i][j]++；但如果不是s[0]，那么dp[i][j] 会等于 dp[i-1][j-1] + dp[i][j-1]，第一项表示t[i-1]之前子序列出现的个数，第二项表示t[i-1]这项出现的次数。为什么是相加，第一项表示不包含t[i-1]这一项的所有可能，第二项表示一定包含了t[i-1] 这一项的可能，根据排列组合？反正列个表推一下就能感受到。

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<long long int>> dp(n+1, vector<long long int>(m+1, 0));
        bool flg = true;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(s[j-1] == t[i-1]) {
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                    if(flg && i==1) {dp[i][j] = 1; flg = false;}
                    else if (i==1) dp[i][j] = dp[i][j-1] + 1;
                    if(dp[i][j] >= 1000000007) dp[i][j] -= 1000000007;
                }
                else dp[i][j] = dp[i][j-1];
            }
            if(flg) break;
        }
        return dp[n][m];
    }
};

代码随想录版本：

  • s[i - 1] 与 t[j - 1]相等
  • s[i - 1] 与 t[j - 1] 不相等

** 当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。

一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。*所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

** 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]

所以递推公式为：dp[i][j] = dp[i - 1][j];

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

相关文章