代码随想录Day 44|leetcode题目:1143.最长公共子序列、1035.不相交的线、53. 最大子序和、392.判断子序列

提示:DDU,供自己复习使用。欢迎大家前来讨论~

文章目录

  • 题目
    • 题目一:1143.最长公共子序列
      • 解题思路:
    • 题目二: 1035.不相交的线
      • 解题思路:
    • 题目三:53. 最大子序和
      • 解题思路
    • 题目四:392.判断子序列
    • 解题思路
      • 1. **确定 dp 数组的含义**
      • 2. **确定递推公式**
      • 3. **初始化 dp 数组**
      • 4. **确定遍历顺序**
      • 5. **举例推导 dp 数组**
      • 6. **代码实现**
    • 总结

动态规划Part11

题目

题目一:1143.最长公共子序列

1143. 最长公共子序列

解题思路:

动规五部曲分析如下:

  1. 确定dp数组(dp table)以及下标的含义

在动态规划中定义dp[i][j]时,选择将字符串的长度定义为[0, i - 1]而非[0, i]的原因主要是为了简化代码实现,特别是在初始化dp数组的第一行和第一列时。这种定义方式可以使得初始化逻辑更加直观和简便。尽管也可以选择[0, i]作为定义方式,但前者在实际操作中更为常见,因为它减少了边界条件处理的复杂性。

  1. 确定递推公式

主要就是两大情况:

  • text1[i - 1] 与 text2[j - 1]相同
  • text1[i - 1] 与 text2[j - 1]不相同

如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。

即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

代码如下:

if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;
} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
  1. dp数组如何初始化

在最长公共子序列问题中,dp[i][0]dp[0][j] 都初始化为0,因为非空字符串与空字符串的最长公共子序列长度为0。其他dp值根据递推关系计算得到。

代码:

vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
  1. 确定遍历顺序

从递推公式,可以看出,有三个方向可以推出dp[i][j],如图:

1143.最长公共子序列

那么为了在递推的过程中,这三个方向都是经过计算的数值,所以要从前向后,从上到下来遍历这个矩阵。

  1. 举例推导dp数组

以输入:text1 = “abcde”, text2 = “ace” 为例,dp状态如图:

1143.最长公共子序列1

最后红框dp[text1.size()][text2.size()]为最终结果

以上分析完毕,C++代码如下:

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));for (int i = 1; i <= text1.size(); i++) {for (int j = 1; j <= text2.size(); j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[text1.size()][text2.size()];}
};
  • 时间复杂度: O(n * m),其中 n 和 m 分别为 text1 和 text2 的长度
  • 空间复杂度: O(n * m)

题目二: 1035.不相交的线

1035. 不相交的线

解题思路:

绘制一些连接两个数字 A[i] 和 B[j] 的直线,只要 A[i] == B[j],且直线不能相交!

直线不能相交,这就是说明在字符串A中 找到一个与字符串B相同的子序列,且这个子序列不能改变相对顺序,只要相对顺序不改变,链接相同数字的直线就不会相交。

拿示例一A = [1,4,2], B = [1,2,4]为例,相交情况如图:

img

其实也就是说A和B的最长公共子序列是[1,4],长度为2。 这个公共子序列指的是相对顺序不变(即数字4在字符串A中数字1的后面,那么数字4也应该在字符串B数字1的后面)

这么分析完之后,大家可以发现:本题说是求绘制的最大连线数,其实就是求两个字符串的最长公共子序列的长度!

本题代码如下:

class Solution {
public:int maxUncrossedLines(vector<int>& A, vector<int>& B) {vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));for (int i = 1; i <= A.size(); i++) {for (int j = 1; j <= B.size(); j++) {if (A[i - 1] == B[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[A.size()][B.size()];}
};
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

题目三:53. 最大子序和

53. 最大子数组和

解题思路

这次我们用动态规划的思路再来分析一次。

动规五部曲如下:

  1. 确定dp数组(dp table)以及下标的含义

dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]

  1. 确定递推公式

dp[i]只有两个方向可以推出来:

  • dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和
  • nums[i],即:从头开始计算当前连续子序列和

一定是取最大的,所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

  1. dp数组如何初始化

从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态,dp[0]就是递推公式的基础。

dp[0]应该是多少呢?

根据dp[i]的定义,很明显dp[0]应为nums[0]即dp[0] = nums[0]。

  1. 确定遍历顺序

递推公式中dp[i]依赖于dp[i - 1]的状态,需要从前向后遍历。

  1. 举例推导dp数组

以示例一为例,输入:nums = [-2,1,-3,4,-1,2,1,-5,4],对应的dp状态如下: 53.最大子序和(动态规划)

注意最后的结果可不是dp[nums.size() - 1]! ,而是dp[6]。

以上动规五部曲分析完毕,完整代码如下:

class Solution {
public:int maxSubArray(vector<int>& nums) {if (nums.size() == 0) return 0;vector<int> dp(nums.size());dp[0] = nums[0];int result = dp[0];for (int i = 1; i < nums.size(); i++) {dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值}return result;}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

题目四:392.判断子序列

392. 判断子序列

解题思路

这个问题是判断一个字符串 s 是否为另一个字符串 t 的子序列。以下是解决这个问题的动态规划方法的关键步骤:

1. 确定 dp 数组的含义

  • dp[i][j] 表示字符串 s 的前 i 个字符和字符串 t 的前 j 个字符的最长相同子序列的长度。

2. 确定递推公式

  • 如果 s[i-1] 等于 t[j-1],则 dp[i][j] = dp[i-1][j-1] + 1
  • 如果 s[i-1] 不等于 t[j-1],则 dp[i][j] = dp[i][j-1],相当于在 t 中跳过字符 t[j-1]

3. 初始化 dp 数组

  • dp[0][j] 初始化为 0,表示空字符串 s 与任意前缀的 t 的子序列长度为 0。
  • dp[i][0] 同理,初始化为 0。

4. 确定遍历顺序

  • 从左到右、从上到下遍历,因为 dp[i][j] 的值依赖于其左边和上边的值。

5. 举例推导 dp 数组

  • 通过具体例子(如 s = "abc"t = "ahbgdc")来手动计算 dp 数组,验证递推公式的正确性。

6. 代码实现

class Solution {
public:bool isSubsequence(string s, string t) {int m = s.size(), n = t.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));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] + 1;elsedp[i][j] = dp[i][j - 1];}}return dp[m][n] == m;}
};
  • 时间复杂度:O(n × m),其中 nm 分别是字符串 st 的长度。
  • 空间复杂度:O(n × m),用于存储 dp 数组。

这种方法确保了通过动态规划有效计算两个字符串的最长相同子序列的长度,从而判断 s 是否为 t 的子序列。

总结

  1. 只考虑了编辑距离中的删除操作,而没有涉及插入和替换,这降低了问题的复杂性。
  2. 动态规划应用:通过动态规划方法,使用二维数组 dp 来记录和计算子问题的解,其中 dp[i][j] 表示考虑字符串 s 的前 i 个字符和字符串 t 的前 j 个字符时的最长相同子序列的长度。
  3. 状态转移
    • 匹配情况:如果 s[i - 1] 等于 t[j - 1],则在之前的基础上增加1,即 dp[i][j] = dp[i - 1][j - 1] + 1
    • 不匹配情况:如果 s[i - 1] 不等于 t[j - 1],则取忽略 s 的当前字符或忽略 t 的当前字符所得到的最大长度,即 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/424727.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Android 13源码分析】WindowContainer窗口层级-3-实例分析

在安卓源码的设计中&#xff0c;将将屏幕分为了37层&#xff0c;不同的窗口将在不同的层级中显示。 对这一块的概念以及相关源码做了详细分析&#xff0c;整理出以下几篇。 【Android 13源码分析】WindowContainer窗口层级-1-初识窗口层级树 【Android 13源码分析】WindowCon…

优化 TCP 以提高网络性能

本页面简要介绍了计算正确设置的方法&#xff0c;以缩短 Google Cloud 和混合场景中 TCP 连接的延迟时间。本页面还可帮助您了解如何缩短 Google Cloud 中流程之间的连接延迟时间。 现代微服务架构主张&#xff0c;开发者应该构建处理单一任务的小型服务。服务应根据系统的可靠…

【iOS】dismiss多级的方法

前言 上次笔者总结过push和pop推入和推出界面的方法&#xff0c;这里对于dismiss多级的方法进行一个总结&#xff0c;推入推出方法可以看看笔者这篇博客&#xff1a;【iOS】UI学习——界面切换 dismiss推出多级的原理 当我们使用pop推入新的界面的时候&#xff0c;连续pop推…

在线查看 Android 系统源代码 AOSPXRef and AndroidXRef

在线查看 Android 系统源代码 AOSPXRef and AndroidXRef 1. AOSPXRef1.1. http://aospxref.com/android-14.0.0_r2/1.2. build/envsetup.sh 2. AndroidXRef2.1. http://androidxref.com/9.0.0_r3/2.2. build/envsetup.sh 3. HELLO AndroidReferences 1. AOSPXRef http://aospx…

YOLOv5/v8 + 双目相机测距

yolov5/v8双目相机测距的代码&#xff0c;需要相机标定 可以训练自己的模型并检测测距&#xff0c;都是python代码 已多次实验&#xff0c;代码无报错。 非常适合做类似的双目课题&#xff01; 相机用的是汇博视捷的双目相机&#xff0c;具体型号见下图。 用的yolov5是6.1版本的…

QT --- 初识QT

一、通过代码构建helloworld界面 一般通过代码来构造界面的时候&#xff0c;通常会把构造界面的代码放到Widget/MainWindow的构造函数中。 Qt中每个类都有对应同名的头文件 上古时期&#xff0c;Qt用的是这种风格的文件。1998年之后&#xff0c;C标准成立了&#xff0c;C98标准…

jenkins入门

CI 、CD入门 一:jenkins实现CI操作 1.在jenkins环境安装jdk 、maven ,同事修改maven里的settings.xml中的两个配置:添加jdk插件版本并开启和私服镜像(也可以在jenkins页面的全局配置选择自动安装,但是自动安装速度很慢,所以这里选择手动安装,后面直接在全局配置指定目…

太阳下山还有月光,月亮睡了还有朝阳

最近听到一首歌《GooGoo-不要慌太阳下山有月光》&#xff0c;觉得里面的歌词很有意思&#xff0c;这也是标题的由来。截取歌词片段&#xff1a; 不要迷茫 不要慌张 太阳下山 还有月光 它会把人生路照亮 陪你到想去的地方 不要彷徨 不要沮丧 月亮睡了 还有朝阳 抬头看天一定会亮…

如何正确使用MMPI量表进行测试?

1、需要初中以上学历&#xff0c;能对测试题准确的理解。 2、应在安静、无干扰的环境中进行&#xff0c;确保自己能够集中注意力完成测试。 3、尽量不要选择“无法回答”这个选项&#xff0c;当然如果确实有无法回答的&#xff0c;也可以选&#xff0c;但是总数不要超过22个。…

Python计算机视觉 第9章-图像分割

Python计算机视觉 第9章-图像分割 图像分割是将一幅图像分割成有意义区域的过程。区域可以是图像的前景与背景或图像中一些单独的对象。这些区域可以利用一些诸如颜色、边界或近邻相似性等特征进行构建。 9.1 图割&#xff08;Graph Cut&#xff09; 图割&#xff08;Graph…

一步一步自制py脚本并且并且修改为exe可执行文件教学外附带SHA-1解密exe文件资源

第一步&#xff1a;安装 Python 下载 Python&#xff1a;访问 Python 官网 下载并安装最新版本的 Python。安装时选择添加到环境变量 PATH&#xff1a;在安装过程中&#xff0c;确保勾选“Add Python to PATH”选项。 第二步&#xff1a;编写 Python 脚本 创建一个新的 Pyth…

基于BiGRU+Attention实现风力涡轮机发电量多变量时序预测(PyTorch版)

前言 系列专栏:【深度学习&#xff1a;算法项目实战】✨︎ 涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域&#xff0c;讨论了各种复杂的深度神经网络思想&#xff0c;如卷积神经网络、循环神经网络、生成对…

参赛心得和思路分享:2021第二届云原生编程挑战赛2: 实现一个柔性集群调度机制

关联比赛: 2021第二届云原生编程挑战赛2&#xff1a;实现一个柔性集群调度机制 参赛心得 历时快两个月的第二届云原生编程挑战赛结束了&#xff0c;作为第一次参赛的萌新&#xff0c;拿下了28名的成绩&#xff0c;与第一名差了19万分&#xff0c;因为赛制时间太长&#xff0c…

基于python+django+vue的社区爱心养老管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于pythondjangovueMySQL的社…

103.WEB渗透测试-信息收集-FOFA语法(3)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;102.WEB渗透测试-信息收集-FOFA语法&#xff08;2&#xff09; FOFA使用实例 组件框架 …

eureka.client.service-url.defaultZone的坑

错误的配置 eureka: client: service-url: default-zone: http://192.168.100.10:8080/eureka正确的配置 eureka: client: service-url: defaultZone: http://192.168.100.10:8080/eureka根据错误日志堆栈打断电调试 出现两个key&#xff0c;也就是defaultZone不支持snake-c…

cmd命令

常用命令 查看电脑名称&#xff1a; hostname 查看网卡信息&#xff1a; ipconfig 快速打开网络设置界面&#xff1a; control.exe netconnections 或 rundll32.exe shell32.dll,Control_RunDLL ncpa.cpld 打开防火墙设置&#xff1a; wf.msc 指定网卡设置IP地址&#…

Vue:使用v-model绑定的textarea在光标处插入指定文本

一、问题描述 使用v-model绑定的textarea如果需要改变其内容&#xff0c;一般只要改变v-model对应的变量即可&#xff0c;但如果需要在textarea的当前光标位置插入指定文本&#xff0c;那就需要操作DOM了。于是我们写了一段js&#xff1a; const insertTextAtCursor (text) …

基于TCP发送北斗消息给船舶设备终端

文章目录 引言I 自定义动态数据交换协议信息交换接口通信格式消息发送指令状态码错误信息返回指令II Netty实现TCP客户端III Java 原始API实现TCP客户端知识扩展: 基于Netty的定位数据平台通信协议定位方式移动定位设备see also引言 需求:发送北斗消息给船舶设备终端 动态信…

windows安装docker、elasticsearch、kibana、cerebro、logstash

文章目录 1. 安装docker1.1. 两大要点1.1.1. 安装启用hyper-v电脑不存在hyper-v的情况 1.1.2. 下载安装docker 2. 在docker里面安装elasticSearch&#xff0c;kibana&#xff0c;cerebro3. 安装logstash-将数据导入到elasticSearch3.1 安装logstash3.1.1 注意事项3.1.1.1. 等了…