代码随想录刷题day53|最长公共子序列不相交的线最大子序和

本文主要是介绍代码随想录刷题day53|最长公共子序列不相交的线最大子序和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • day53学习内容
  • 一、最长公共子序列
    • 1.1、动态规划五部曲
      • 1.1.1、 确定dp数组(dp table)以及下标的含义
      • 1.1.2、确定递推公式
      • 1.1.3、 dp数组如何初始化
      • 1.1.4、确定遍历顺序
      • 1.1.5、输出结果
    • 1.2、代码
  • 二、不相交的线
    • 2.1、动态规划五部曲
      • 2.1.1、 确定dp数组(dp table)以及下标的含义
      • 2.1.2、确定递推公式
      • 2.1.3、 dp数组如何初始化
      • 2.1.4、确定遍历顺序
      • 2.1.5、输出结果
    • 2.2、代码
  • 三、最大子序和
    • 3.1、动态规划五部曲
      • 3.1.1、 确定dp数组(dp table)以及下标的含义
      • 3.1.2、确定递推公式
      • 3.1.3、 dp数组如何初始化
      • 3.1.4、确定遍历顺序
      • 3.1.5、输出结果
    • 3.2、代码
  • 总结
    • 1.感想
    • 2.思维导图


day53学习内容

day53主要内容

  • 最长公共子序列
  • 不相交的线
  • 最大子序和

声明
本文思路和文字,引用自《代码随想录》


一、最长公共子序列

1143.原题链接

1.1、动态规划五部曲

1.1.1、 确定dp数组(dp table)以及下标的含义

  • dp[i][j] 表示字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符的最长公共子序列的长度。

1.1.2、确定递推公式

基本思路
我们可以根据两个字符串中当前字符是否相等,采取不同的策略来更新 dp 表。
与最长公共子数组(或子串)不同,子序列不要求元素在原字符串中是连续的,只要求它们保持相对顺序即可。

推导状态转移方程

  1. 字符匹配的情况
    text1[i-1] == text2[j-1] 时,这意味着这两个字符可以成为目前为止考虑的字符串的公共子序列的一部分。因此,这两个字符将增加公共子序列的长度,即
dp[i][j]=dp[i−1][j−1]+1

这个方程表明,text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列可以通过在它们的前 i-1 个字符和前 j-1 个字符的最长公共子序列的基础上添加这两个匹配的字符来得到。

  1. 字符不匹配的情况
    text1[i-1] != text2[j-1] 时,最长公共子序列不能同时包括这两个字符。因此,有以下两种可能性:
    • 忽略 text1 的当前字符 i-1,只考虑 text1 的前 i-1 个字符和 text2 的前 j 个字符。
    • 忽略 text2 的当前字符 j-1,只考虑 text1 的前 i 个字符和 text2 的前 j-1 个字符。
      这两种情况下的最长公共子序列的长度将是:
dp[i][j]=max(dp[i−1][j],dp[i][j−1])

这个方程表明,当前的 dp[i][j] 应取前面两种情况中更长的子序列长度。

1.1.3、 dp数组如何初始化

  • dp[0][x]dp[x][0] 应该初始化为 0,因为一个长度为 0 的字符串与任何字符串的最长公共子序列长度都是 0。
  • 或者这句话看不懂,就画个图。。。看一下推导的方向就明白了
    在这里插入图片描述
    图引用自卡尔的视频。

https://www.bilibili.com/video/BV1ye4y1L7CQ/?spm_id_from=pageDriver&vd_source=266f115062b99cd2d8e5185add0b8cc9

1.1.4、确定遍历顺序

从小到大遍历

1.1.5、输出结果

  • return dp[text1.length()][text2.length()]; 最后,dp 数组的最后一个元素(即 dp[text1.length()][text2.length()])包含了整个 text1text2 的最长公共子序列的长度。

1.2、代码

class Solution {public int longestCommonSubsequence(String text1, String text2) {// 创建二维数组dp,大小为text1长度+1和text2长度+1int[][] dp = new int[text1.length() + 1][text2.length() + 1];// 遍历text1的每一个字符for (int i = 1; i <= text1.length(); i++) {char char1 = text1.charAt(i - 1); // 获取text1的第i-1个字符// 遍历text2的每一个字符for (int j = 1; j <= text2.length(); j++) {char char2 = text2.charAt(j - 1); // 获取text2的第j-1个字符// 如果两个字符相同if (char1 == char2) {// 如果当前的两个字符相同,则当前dp[i][j]应基于之前的dp[i-1][j-1]的值加1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果两个字符不同,选择之前两种情况的较大者作为当前dp[i][j]的值dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回数组的最后一个元素,即为text1和text2的最长公共子序列长度return dp[text1.length()][text2.length()];}
}

二、不相交的线

1035.原题链接

它实质上和最长公共子序列(LCS)问题相同,只是在不同的上下文中应用。在这个问题中,我们要在两个数组中找到最多的对应数字(或线),使得这些数字的顺序在两个数组中保持一致,但不必连续。

2.1、动态规划五部曲

2.1.1、 确定dp数组(dp table)以及下标的含义

  • 其中 dp[i][j] 代表考虑 nums1 的前 i 个元素和 nums2 的前 j 个元素时的最大不相交线数(或最长公共子序列的长度)。

2.1.2、确定递推公式

  • for (int i = 1; i <= len1; i++):外层循环遍历 nums1
  • for (int j = 1; j <= len2; j++):内层循环遍历 nums2
    • if (nums1[i - 1] == nums2[j - 1]):如果当前考虑的两个元素相等,表示可以在此基础上形成一个新的对应线,所以 dp[i][j] = dp[i - 1][j - 1] + 1;。这意味着我们在之前的最大对应线数的基础上增加一条新的线。
    • else:如果当前的两个元素不相等,则我们需要决定是跳过 nums1 的当前元素还是 nums2 的当前元素,以保持最大的对应线数。因此,dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); 选择这两种情况中较大的一个。

2.1.3、 dp数组如何初始化

根据前面的分析。dp 表的最后一个元素就是两个数组中可以形成的最大不相交线数,这等同于最长公共子序列的长度。所以初始化逻辑和上面那题是一样的,这里不再赘述了。

2.1.4、确定遍历顺序

从小到大遍历

2.1.5、输出结果

  • return dp[len1][len2]; 动态规划表的最后一个元素包含了整个 nums1nums2 可以形成的最大不相交线数。

2.2、代码

class Solution {// maxUncrossedLines 方法用来计算两个数组间的最大未交叉线数public int maxUncrossedLines(int[] nums1, int[] nums2) {// len1 和 len2 分别是两个数组的长度int len1 = nums1.length;int len2 = nums2.length;// dp 数组用于存储动态规划的中间结果int[][] dp = new int[len1 + 1][len2 + 1];// 外层循环遍历 nums1for (int i = 1; i <= len1; i++) {// 内层循环遍历 nums2for (int j = 1; j <= len2; j++) {// 如果当前两个数组的元素相等,更新 dp 数组的值if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 如果不相等,取两种情况的较大值,即不包含当前 nums1 的元素或不包含当前 nums2 的元素dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}// 返回 dp 数组右下角的值,即为最大未交叉线数return dp[len1][len2];}
}

三、最大子序和

53.原题链接

3.1、动态规划五部曲

3.1.1、 确定dp数组(dp table)以及下标的含义

  • dp[i] 表示以第 i 个元素结尾的最大子数组和。

3.1.2、确定递推公式

  • 从数组的第二个元素开始遍历(即i=1)。
  • 对于每个元素nums[i],更新dp[i]。这里的转移方程是:
    • dp[i] = Math.max(dp[i-1] + nums[i], nums[i])
    • 这个方程的意思是,考虑到第i个元素时,最大子数组和可以是:
      • dp[i-1] + nums[i](即包含之前的最大子数组和再加上当前元素nums[i]),或者
      • nums[i]本身(即从新开始计数,只取当前元素,这种情况适用于dp[i-1]是负数,不如放弃之前的累计,重新开始)。
  • 同时更新结果res,如果dp[i]比当前的res还要大,就用dp[i]更新res

3.1.3、 dp数组如何初始化

dp[0]即为nums[0],因为第一个元素前面没有其他元素,所以它自身就是一个子数组。

3.1.4、确定遍历顺序

从小到大遍历

3.1.5、输出结果

最后返回 res,它存储的是整个数组的最大子数组和。

3.2、代码

class Solution {public int maxSubArray(int[] nums) {// 如果数组为空,则直接返回0(通常情况下,这里可以根据题意返回负无穷或抛出异常)if (nums.length == 0) {return 0;}// res用来存储最终的最大子数组和,初值设为数组的第一个元素int res = nums[0];// dp数组用于动态规划存储到当前元素为止的最大子数组和,dp[0]自然是第一个元素int[] dp = new int[nums.length];dp[0] = nums[0];// 从数组的第二个元素开始遍历for (int i = 1; i < nums.length; i++) {// 动态规划的转移方程:比较“继续当前子数组”与“从新的位置开始”dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);// 更新全局的最大子数组和res = Math.max(res, dp[i]);}// 返回计算得到的最大子数组和return res;}
}

总结

1.感想

  • 补周六的进度,冲

2.思维导图

本文思路引用自代码随想录,感谢代码随想录作者。

这篇关于代码随想录刷题day53|最长公共子序列不相交的线最大子序和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907372

相关文章

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若