首页 > 编程语言 >「代码随想录算法训练营」第三十九天 | 动态规划 part12

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

时间:2024-08-16 08:58:00浏览次数:11  
标签:part12 第三十九 随想录 int word1 https word2 dp size

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

标签:part12,第三十九,随想录,int,word1,https,word2,dp,size
From: https://www.cnblogs.com/frontpen/p/18360135

相关文章

  • 代码随想录Day16
    513.找树左下角的值给定一个二叉树的根节点root,请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7提示:二叉树的节点个数的范围是[1,104]-231<=......
  • 【代码随想录】一、数组:6.前缀和
    二刷的时候发现更新了一些新的题目,尝试写了写后,发现我完全不会ACM输入输出模式。这两天在补前几天没背的八股,写得不够满意(几乎是完全誊代码了),先放着,后面再补充补充吧。1.题目:44.开发商购买土地#include<iostream>#include<vector>#include<climits>usingnamespacestd......
  • 【代码随想录】一、数组:4.滑动窗口
    1.题目1:209.长度最小的子数组1.1.解法1:暴力解法(已超时)使用两层循环,外层循环确定最小子数组开始的位置(i),内层循环确定最小子数组结束的位置(j)。在每次跳出内层循环时,sum应重置为0。当找到的子数组相加的和等于或大于目标值(target)时,算出此刻子数组的长度(j-i+1),并更新result的值......
  • 【代码随想录】一、数组:5.螺旋矩阵
    本题并不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。1.题目1:59.螺旋矩阵II1.1.解法1:模拟本题的重点还是像之前的“704.二分查找”,坚持循环不变量原则,即在本题中遍历每条边时,坚持相同的原则。如下是一个示例,即n=5,我们考虑根据圈数和边数来进行遍历:由外圈到内......
  • 代码随想录算法训练营 | 动态规划 part01
    509.斐波那契数509.斐波那契数状态转移方程:F(0)=0,F(1)=1F(n)=F(n-1)+F(n-2),其中n>1递归,太多重复计算classSolution{public:intfib(intn){if(n==0||n==1){returnn;}returnfib(n-1)......
  • 代码随想录算法训练营第一天 | 704. 二分查找,27. 移除元素
     704.二分查找题目链接:https://leetcode.cn/problems/binary-search/1,左闭右闭publicintsearch(int[]nums,inttarget){intlow=0;inthigh=nums.length-1;while(low<=high){intmid=(high+low)/2;if(num......
  • 代码随想录算法训练营第43天:动态规划part10:子序列问题
    300.最长递增子序列力扣题目链接(opensnewwindow)给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例1:输入:nums=[10,9,2......
  • 代码随想录day30 || 452 引爆气球,435 无重叠区间,763 划分字母区间
    452射爆气球funcfindMinArrowShots(points[][]int)int{ //思路,尝试按照startasc,endasc排序一下,取交集射爆 iflen(points)==1{ return1 } sort.Slice(points,func(i,jint)bool{ ifpoints[i][0]==points[j][0]{ returnpoints[i][1]<points......
  • 代码随想录Day15
    110.平衡二叉树(优先掌握递归)给定一个二叉树,判断它是否是平衡二叉树平衡二叉树是指该树所有节点的左右子树的深度相差不超过1。示例1:输入:root=[3,9,20,null,null,15,7]输出:true示例2:输入:root=[1,2,2,3,3,null,null,4,4]输出:false示例3:输入:root=[]输出:t......
  • 【代码随想录】一、数组:3.双指针 - 977.有序数组的平方
    本文为977.有序数组的平方的解法,部分图文参考自代码随想录977.有序数组的平方。1.题目1:977.有序数组的平方1.1.解法1:直接排序classSolution{public:vector<int>sortedSquares(vector<int>&nums){for(inti=0;i<nums.size();i++){n......