300. 最长递增子序列
题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
思路分析
最长上升子序列是动规的经典题目，这里dp[i]是可以根据dp[j] （j < i）推导出来的，那么依然用动规五部曲来分析详细一波：
dp[i]的定义
dp[i]表示i之前包括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,遍历i的循环在外层,遍历j则在内层.也是从前往后遍历
举例推导dp数组
输入：[0,1,0,3,2]，dp数组的变化如下：
参考代码
#include<bits/stdc++.h> using namespace std; int lengthOfLIS(vector<int>& nums) { if(nums.size()==1){ return 1; } vector<int> dp(nums.size(),1);//初始化为1 int result = 0;//保存最大序列的结果 for(int i = 1; i<nums.size();i++) {//外层遍历所有的数 for(int j = 0; j < i;j++){//内层遍历概述之前的数,本质是找出小于i所有的序列,如x if(nums[i]>nums[j]){//如果 序列 x的最后一个数字 小于当前的数字,则当前数字可以加入该序列.否则无法形成. dp[i] = max(dp[i],dp[j]+1); } } if(dp[i] > result){//更新最大序列的长度 result = dp[i]; } } return result; }
674. 最长连续递增序列
题目描述
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2] 输出：1 解释：最长连续递增序列是 [2], 长度为1。
思路分析
本题相对于上题区别在于 “连续”,本题要求的是最长连续序列
动规五部曲
确定dp数组以及下标的含义
dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]
确定递推公式
如果nums[i+1] > nums[i],那么以i+1 为结尾的数组的连续递增的子序列长度一定等于 以i为结尾的数组的连续底层的子序列长度 + 1. 即: dp[i+1] = dp[i] + 1;
**注意:**因为求的是连续递增子序列,所以就只需要比较nums[i+1]与nums[i].所以本题一层for循环就可以了.
dp数组进行初始化
每一个i,对应的dp[i] (即最长连续递增子序列)起始大小至少都是1.这个很好理解,最少也是自己本身的长度嘛
确定遍历顺序
从递推公式可有看出,dp[i+1]依赖于dp[i],所以一定是从前往后遍历.
举例推导dp数组
已输入nums = [1,3,5,4,7]为例，dp数组状态如下：
参考代码
#include<bits/stdc++.h> using namespace std; int findLengthOfLCIS(vector<int>& nums) { if(nums.size()==1){ return 1; } vector<int> dp(nums.size(),1) ;//定义dp int result = 0;//保存最长连续递增序列的长度 //递推 for(int i = 1; i < nums.size();i++) {//遍历所有的元素 if(nums[i-1]<nums[i]){//如果当前元素比前一个元素大 (因为是连续,所以只需要判断前一个是否和当前连续递增即可) dp[i] = dp[i-1]+1; } if(dp[i]>result){//更新结果集 result = dp[i]; } } return result; }
718. 最长重复子数组
题目描述
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出：5
思路分析
题目说的是求公共最长子数组,其实就是求连续子序列.
动规五部曲
确定dp数组及下标含义
dp[i] [j]:以下标i-1结尾的A和以下标j-1为结尾的B,最长重复子数组长度为dp[i] [j].
那么有细心的小可爱可能问了,dp[i] [j]为啥不表示成 下标i为结尾的A和以下标j为结尾的B,这样不可以么?
如果这样的话dp[0] [0]=dp[-1] [-1]+1了.初始化条件就没法搞了… 不方便.
确定递推公式
根据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
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.
确定遍历顺序
外层for循环遍历A,内层for循环遍历B.(反之也可)
举例推导dp数组
拿示例1中，A: [1,2,3,2,1]，B: [3,2,1,4,7]为例，画一个dp数组的状态变化，如下：
参考代码
#include<bits/stdc++.h> using namespace std; int findLength(vector<int>& nums1, vector<int>& nums2) { vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));//dp定义以及初始化 dp[i][j]:nums1[i-1]结尾的数组和 以nums2[j-1]结尾的数组的 子数组的长度. int result = 0;//为啥不用dp[i][j] 表示:nums1[i],nums2[j] 结尾的子数组的最大长度呢?? 因为如果这样的话dp[0][0]=dp[-1][-1]+1了.初始化条件就没法搞了... //递推dp for(int i = 1; i <=nums1.size(); i++) { for(int j = 1; j<= nums2.size(); j++) { if(nums1[i-1]==nums2[j-1]) { //如果 nums1[i-1]和nums2[i-1]相等,则 dp[i][j] = dp[i-1][j-1] + 1;//当前子数组(以nums1[i-1][j-1])长度 = 之前子数组长度+1 } if(result < dp[i][j]) { //更新result result = dp[i][j]; } } } return result; }
