「代码随想录算法训练营」第三十九天 | 动态规划 part12

115. 不同的子序列

题目链接:https://leetcode.cn/problems/distinct-subsequences/
文章讲解:https://programmercarl.com/0115.不同的子序列.html
题目难度:困难
视频讲解:https://www.bilibili.com/video/BV1fG4y1m75Q/
题目状态:看题解

思路:

  1. 动态规划数组初始化
    • 创建一个二维动态规划数组 dp,大小为 ((s.size() + 1), (t.size() + 1))。dp[i][j] 表示 s 的前 i 个字符中包含 t 的前 j 个字符的不同子序列的数量。
  2. 边界条件设置
    • dp[i][0] = 1:表示任何字符串 s 的前 i 个字符都可以形成空字符串 t 的一种方式(即选择不选)。
    • dp[0][j] = 0(对于 (j > 0)):表示空字符串 s 无法形成非空字符串 t
  3. 动规数组更新
    • 外层循环遍历 s 的每个字符(从 1s.size())。
    • 内层循环遍历 t 的每个字符(从 1t.size())。
    • 如果 s[i-1]t[j-1] 相等:
      • dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]:表示可以选择将这个字符包含在子序列中(加上 dp[i-1][j-1])或者不包含(加上 dp[i-1][j])。
    • 如果不相等:
      • dp[i][j] = dp[i - 1][j]:只能选择不包含 s[i-1]
  4. 结果
    • 返回 dp[s.size()][t.size()],即 s 中包含 t 的不同子序列的数量。

代码:

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

583. 两个字符串的删除操作

题目链接:https://leetcode.cn/problems/delete-operation-for-two-strings/
文章讲解:https://programmercarl.com/0583.两个字符串的删除操作.html
题目难度:中等
视频讲解:https://www.bilibili.com/video/BV1we4y157wB/
题目状态:看题解

思路:

维护一个二维动规数组dp[i][j]用来表示将word1的前i个字符转换为word2的前j个字符所需的最小操作次数。

初始化dp[i][j]

  • dp[i][0] = i:将word1的前i个字符转换为空字符串需要i次删除操作。
  • dp[0][j] = j:将空字符串转换为word2的前j个字符需要j次插入操作。

更新动规数组:
对于每一对ij,我们考虑以下两种情况:

  • 字符匹配(word1[i-1] == word2[j-1]):
    • 如果当前字符相同,不需要任何操作: dp[i][j] = dp[i - 1][j - 1];
  • 字符不匹配(word1[i-1] != word2[j-1]):
    • 我们可以进行两种操作:
      • 删除一次word1的元素:此时需要dp[i - 1][j] + 1次操作次数。
      • 删除一次word2的元素:此时需要dp[i][j - 1] + 1此操作次数。
    • 取这两种操作的最小值:min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)

代码:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size(), len2 = word2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
        for(int i = 0; i <= len1; ++i) dp[i][0] = i;
        for(int j = 0; j <= len2; ++j) dp[0][j] = j;
        for(int i = 1; i <= len1; ++i) {
            for(int j = 1; j <= len2; ++j) {
                if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            }
        }
        return dp[len1][len2];
    }
};

72. 编辑距离

题目链接:https://leetcode.cn/problems/edit-distance/
文章讲解:https://programmercarl.com/0072.编辑距离.html
题目难度:中等
视频讲解:https://www.bilibili.com/video/BV1qv4y1q78f/
题目状态:有思路,细节出了问题

思路:

这道题的本质就是在上道题的基础上做了改变,上道题遇到不相等的字符时只需要考虑删除操作,这道题在遇到不相等的字符时需要考虑三种情况:删除、插入、替换。

  • 删除:在word1中删除一个字符,也就转化为了word1[i - 2]word2[j - 1]相比较了,因此dp[i][j] = dp[i - 1][j] + 1
  • 插入:在word1中添加一个字符,其实这个操作得到的最终结果和在word2中删除一个字符的结果是一样的,因此就转化为word1[i - 1]word2[j - 2]相比较了,因此dp[i][j] = dp[i][j - 1] + 1
  • 替换:替换操作就是在word1[i - 1] != word2[j - 1]的前提下进行一次操作使得word1[i - 1] == word2[j - 1],因此dp[i][j] = dp[i - 1][j - 1] + 1

最终取这三个操作的最小值即可。

代码:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size(), len2 = word2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
        for(int i = 0; i <= len1; ++i) dp[i][0] = i;
        for(int j = 0; j <= len2; ++j) dp[0][j] = j;
        for(int i = 1; i <= len1; ++i) {
            for(int j = 1; j <= len2; ++j) {
                if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
            }
        }
        return dp[len1][len2];
    }
};

热门相关:重生之神级败家子   诱妻入怀:老公,手下留情!   大首长,小媳妇   爆萌宠妃:狼性邪帝,吃不够   Hello,校草大人!