力扣爆刷第80天--动态规划一网打尽子序列一维二维连续不连续变体

本文主要是介绍力扣爆刷第80天--动态规划一网打尽子序列一维二维连续不连续变体,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣爆刷第80天–动态规划一网打尽子序列一维二维连续不连续变体

文章目录

      • 力扣爆刷第80天--动态规划一网打尽子序列一维二维连续不连续变体
      • 零、总结
      • 一、1035.不相交的线
      • 二、53. 最大子序和
      • 三、392.判断子序列
      • 四、115.不同的子序列

零、总结

今天也是子序列的一天,但和上一期不同的是都是变体,也分为一维、二维、连续、非连续四种题型。
另外就是做子序列相关的题目一定要考虑好定义以后就使用实例自己推导一下,把结果展现出来,然后再看看能否推导出递推公式或者看看递推公式是否匹配。

一、1035.不相交的线

题目链接:https://leetcode.cn/problems/uncrossed-lines/description/
思路:本题不相交的线其实是求最长重复子序列,只是把题目的问法稍微改动了一点,但本质没有变,子序列具体的四种类型上一期有讲,本期不再赘述。
定义dp[i][j]表示区间nums1[0, i]和区间nums2[0, j]中以nums1[i]和nums2[j]为结尾的最长重复子序列的长度,那么如果nums1[i]==num2s[j],dp[i][j]自然可以从dp[i-1][j-1]推出,为dp[i][j] = dp[i-1][j-1] + 1;
如果nums1[i] != num2s[j],那么最长的长度要延续之前的长度,dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];for(int i = 1; i <= nums1.length; i++) {for(int j = 1; j <= nums2.length; j++) {if(nums1[i-1] == nums2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);}}}return dp[nums1.length][nums2.length];}
}

二、53. 最大子序和

题目链接:https://leetcode.cn/problems/maximum-subarray/
思路:本题求的是最大和的连续子数组,是一维的,和上一期中的最长连续递增子序列是一类题目,只不过算个变体,改变了问法,但解题的方法没有变,依然是定义dp[i]表示为nums[0, i]中以nums[i]为结尾的连续子数组的最大和,那么对于每一个元素来说,是否加到上一个连续子数组的结尾,取决于加上后,和的值是否变大,不变大就另起炉灶,由此可以得到递推公式:dp[i] = Math.max(nums[i], dp[i-1]+nums[i]);

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int max = nums[0];for(int i = 1; i < nums.length; i++) {dp[i] = Math.max(nums[i], dp[i-1]+nums[i]);max = Math.max(max, dp[i]);}return max;}
}

贪心:
另外本题使用贪心也可以做,求最大连续子数组的和,只要连续子数组的和大于0,就可以相加,如果小于0,便新开一个子数组。

class Solution {public int maxSubArray(int[] nums) {int sum = 0, max = Integer.MIN_VALUE;for(int i = 0; i < nums.length; i++) {sum += nums[i];max = Math.max(sum, max);if(sum < 0) {sum = 0;}}return max;}
}

三、392.判断子序列

题目链接:https://leetcode.cn/problems/is-subsequence/
思路:本题是判断s是否是t的子序列,那么也有是一个变体,即s是连续,t非连续,上一期的是s与t都连续,或者都不连续,且看本题如何解决。
定义dp[i][j]表示,s[0, i] 和 t[0, j]中以s[i]为结尾,且以t[j]为结尾,是否为其子序列,如果s[i]==t[j]根据定义,延续dp[i-1][j-1]的状态,如果s[i] != t[j],应该延续,s[i]与t[j-1]的状态,如s = “b”, t = “abc” , 求dp[1][3],b与c不等,应该继承 “b” 与 "ab"的状态。

class Solution {public boolean isSubsequence(String s, String t) {if(s.length() > t.length()) return false;if(s.length() == 0) return true;boolean[][] dp = new boolean[s.length()+1][t.length()+1];Arrays.fill(dp[0], true);for(int i = 1; i <= s.length(); i++) {for(int j = 1; j <= t.length(); j++) {if(s.charAt(i-1) == t.charAt(j-1)) {dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = dp[i][j-1];}}}return dp[s.length()][t.length()];}
}

双指针:
下面的写法丑陋了一些,但也是双指针,调整了t的遍历位置。

class Solution {public boolean isSubsequence(String s, String t) {int len = 0, k = 0;for(int i = 0; i < s.length(); i++) {for(int j = k; j < t.length(); j++) {if(s.charAt(i) == t.charAt(j)) {len++;k = j+1;break;}}}return len == s.length();}
}

四、115.不同的子序列

题目链接:https://leetcode.cn/problems/distinct-subsequences/
思路:本题也是变体,s不连续,t连续,和上一题是类似的,但是求的目标变成了组合数,依然定义为dp[i][j]表示为s[0, i]和t[0, j]以s[i]和t[j]为结尾,t出现在s中的组合数,那么当s[i]==t[j]时,不光可以记录下s[i-1]和t[j-1]的组合数,也可以记录下s[i-1]和t[j]的组合数,不等时,只需要记录s[i-1]与t[j]的组合数,具体可以简单推导一下。

class Solution {public int numDistinct(String s, String t) {int[][] dp = new int[s.length()+1][t.length()+1];for(int i = 0; i < s.length(); i++) {dp[i][0] = 1;}for(int i = 1; i <= s.length(); i++) {for(int j = 1; j <= t.length(); j++) {if(s.charAt(i-1) == t.charAt(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.length()][t.length()];}
}

这篇关于力扣爆刷第80天--动态规划一网打尽子序列一维二维连续不连续变体的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

uva 10131 最长子序列

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

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能