侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第五十五天 | 判断子序列;不同的子序列

thinkTV
2023-06-12 / 0 评论 / 0 点赞 / 161 阅读 / 913 字 / 正在检测是否收录...

1. 判断子序列

代码随想录:原文

力扣题目:392.判断子序列

1.1 思路

动态规划五部曲

  1. 确定dp数组(dp table)以及下标的含义
  • dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]
  1. 确定递推公式
  • if (s[i - 1] == t[j - 1]): t中找到了一个字符在s中也出现了
    • dp[i][j] = dp[i - 1][j - 1] + 1;
  • if (s[i - 1] != t[j - 1]):相当于t要删除元素,继续匹配
    • dp[i][j] = dp[i][j - 1];

最长公共子序列的递推公式基本那就是一样的,区别就是本题如果删元素一定是字符串t,而 最长公共子序列 是两个字符串都可以删元素

  1. dp数组如何初始化
  • dp[i][0] 表示以下标i-1为结尾的字符串,与空字符串的相同子序列长度,所以为0.
  • dp[0][j]同理
  1. 确定遍历顺序
  • 从上到下,从左到右
  1. 举例推导dp数组
  • 输入:s = “abc”, t = “ahbgdc”,dp状态转移图如下:

图片-1

1.1 代码实现

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 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] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
        if (dp[s.size()][t.size()] == s.size()) return true;
        return false;
    }
};

2. 不同的子序列

代码随想录:原文

力扣题目:115.不同的子序列

2.1 思路

动规五部曲

  1. 确定dp数组(dp table)以及下标的含义
  • dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
  1. 确定递推公式
  • 当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] = dp[i - 1][j];
  1. dp数组如何初始化
  • dp[i][0] 表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数:1
  • dp[0][j]:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数:0
vector<vector<long long>> dp(s.size() + 1, vector<long long>(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; // 其实这行代码可以和dp数组初始化的时候放在一起,但我为了凸显初始化的逻辑,所以还是加上了。
  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];
        }
    }
}

  1. 举例推导dp数组

以s:“baegg”,t:"bag"为例,推导dp数组状态如下

图片-2

2.2 代码实现

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()];
    }
};
0

评论区