织梦建站要多少钱,外包公司的招聘专员好干吗,杨浦网站建设,网站制作厂家有哪些代码随想录算法训练营第五十二天 | 300.最长递增子序列#xff0c;674. 最长连续递增序列#xff0c;718. 最长重复子数组 300.最长递增子序列674. 最长连续递增序列718. 最长重复子数组 300.最长递增子序列
题目链接 视频讲解 给你一个整数数组 nums #xff0c;找到其中最… 代码随想录算法训练营第五十二天 | 300.最长递增子序列674. 最长连续递增序列718. 最长重复子数组 300.最长递增子序列674. 最长连续递增序列718. 最长重复子数组 300.最长递增子序列
题目链接 视频讲解 给你一个整数数组 nums 找到其中最长严格递增子序列的长度子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
输入nums [10,9,2,5,3,7,101,18]
输出4dp[i]的定义 本题中正确定义dp数组的含义十分重要 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度为什么一定表示 “以nums[i]结尾的最长递增子序” 因为我们在 做 递增比较的时候如果比较 nums[j] 和 nums[i] 的大小那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾 要不然这个比较就没有意义了不是尾部元素的比较那么 如何算递增呢 状态转移方程 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值 所以if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1); 注意这里不是要dp[i] 与 dp[j] 1进行比较而是我们要取dp[j] 1的最大值 dp[i]的初始化 每一个i对应的dp[i]即最长递增子序列起始大小至少都是1. 确定遍历顺序 dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来那么遍历i一定是从前向后遍历 j其实就是遍历0到i-1那么是从前到后还是从后到前遍历都无所谓只要吧 0 到 i-1 的元素都遍历了就行了 遍历i的循环在外层遍历j则在内层代码如下
for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);}if (dp[i] result) result dp[i]; // 取长的子序列
}举例推导dp数组 输入[0,1,0,3,2]dp数组的变化如下
class Solution {
public:int lengthOfLIS(vectorint nums) {if (nums.size() 1) return nums.size();vectorint dp(nums.size(), 1);int result 0;for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);}if (dp[i] result) result dp[i]; // 取长的子序列}return result;}
};674. 最长连续递增序列
题目链接 视频讲解 给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], …, nums[r - 1], nums[r]] 就是连续递增子序列
输入nums [1,3,5,4,7]
输出3动规五部曲分析如下 确定dp数组dp table以及下标的含义 dp[i]以下标i为结尾的连续递增的子序列长度为dp[i] 注意这里的定义一定是以下标i为结尾并不是说一定以下标0为起始位置 确定递推公式 如果 nums[i] nums[i - 1]那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 1即dp[i] dp[i - 1] 1; 因为本题要求连续递增子序列所以就只要比较nums[i]与nums[i - 1]而不用去比较nums[j]与nums[i] j是在0到i之间遍历既然不用j了那么也不用两层for循环本题一层for循环就行比较nums[i] 和 nums[i - 1] dp数组如何初始化 以下标i为结尾的连续递增的子序列长度最少也应该是1即就是nums[i]这一个元素 所以dp[i]应该初始1; 确定遍历顺序 从递推公式上可以看出 dp[i 1]依赖dp[i]所以一定是从前向后遍历 本文在确定递推公式的时候也说明了为什么本题只需要一层for循环代码如下
for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) { // 连续记录dp[i] dp[i - 1] 1;}
}举例推导dp数组 已输入nums [1,3,5,4,7]为例dp数组状态如下 注意这里要取dp[i]里的最大值所以dp[2]才是结果
class Solution {
public:int findLengthOfLCIS(vectorint nums) {if (nums.size() 0) return 0;int result 1;vectorint dp(nums.size() ,1);for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) { // 连续记录dp[i] dp[i - 1] 1;}if (dp[i] result) result dp[i];}return result;}
};718. 最长重复子数组
题目链接 视频讲解 给两个整数数组 nums1 和 nums2 返回 两个数组中 公共的 、长度最长的子数组的长度
输入nums1 [1,2,3,2,1], nums2 [3,2,1,4,7]
输出3确定dp数组dp table以及下标的含义 dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]。 特别注意 “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 那dp[0][0]是什么含义呢总不能是以下标-1为结尾的A数组吧其实dp[i][j]的定义也就决定着我们在遍历dp[i][j]的时候i 和 j都要从1开始 那有人问了定义dp[i][j]为 以下标i为结尾的A和以下标j 为结尾的B最长重复子数组长度。不行么行倒是行 但实现起来就麻烦一点需要单独处理初始化部分在本题解下面的拓展内容里我给出了 第二种 dp数组的定义方式所对应的代码和讲解大家比较一下就了解了 确定递推公式 根据dp[i][j]的定义dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来 即当A[i - 1] 和B[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 1; 根据递推公式可以看出遍历i 和 j 要从1开始 dp数组如何初始化 根据dp[i][j]的定义dp[i][0] 和dp[0][j]其实都是没有意义的 但dp[i][0] 和dp[0][j]要初始值因为 为了方便递归公式dp[i][j] dp[i - 1][j - 1] 1; 所以dp[i][0] 和dp[0][j]初始化为0 举个例子A[0]如果和B[0]相同的话dp[1][1] dp[0][0] 1只有dp[0][0]初始为0正好符合递推公式逐步累加起来 确定遍历顺序 外层for循环遍历A内层for循环遍历B 同时题目要求长度最长的子数组的长度所以在遍历的时候顺便把dp[i][j]的最大值记录下来 代码如下
for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.size(); j) {if (nums1[i - 1] nums2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;}if (dp[i][j] result) result dp[i][j];}
}举例推导dp数组 拿示例1中A: [1,2,3,2,1]B: [3,2,1,4,7]为例画一个dp数组的状态变化如下
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp (nums1.size() 1, vectorint(nums2.size() 1, 0));int result 0;for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.size(); j) {if (nums1[i - 1] nums2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;}if (dp[i][j] result) result dp[i][j];}}return result;}
};
