代码随想录算法训练营第四十八天| 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

300. 最长递增子序列思路首先注意这里的递增不一定要连续可以是隔了几个数字的递增。那么这道题设dp数组的含义比较有意思dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。当nums[i]大于nums[j]的时候我们可以写出状态转移方程。dp[i] max(dp[i], dp[j] 1);其实这里不是和dp[i]在比较而是在取dp[j]1的最大值。热后返回最大的result即可。我的代码class Solution { public: int lengthOfLIS(vectorint nums) { if(nums.size()1) return nums.size(); vectorint dp(nums.size(),1); int result0; for(int i1;inums.size();i) { for(int j0;ji;j) { if(nums[i]nums[j]) dp[i]max(dp[i],dp[j]1); } resultmax(result,dp[i]); } return result; } };674. 最长连续递增序列思路这道题目相比上一道题目简单一点因为你不用动态规划也能想出思路来。那么这题强调连续就说明这里dp数组又是i状态与i-1状态紧密相关。dp[i] dp[i - 1] 1。其他的跟上到题目一样。我的代码class Solution { public: int findLengthOfLCIS(vectorint nums) { if(nums.size()1) return nums.size(); vectorint dp(nums.size(),1); int result0; for(int i1;inums.size();i) { if(nums[i]nums[i-1]) dp[i]dp[i-1]1; resultmax(result,dp[i]); } return result; } };718. 最长重复子数组思路这道题目相对比较难需要定义一个二维dp数组dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]。为什么是i-1和j-1呢因为这样初始化比较方便一点。同样的这里子数组是强调连续的所以递归状态需要从i-1和j-1推出来即当A[i - 1] 和B[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 1;初始化就全部初始化成0就可以了因为dp[0][0]理论上不能由前一个状态得出初始化成0刚好。剩下就依旧是取最大值的操作了。我的代码class Solution { public: int findLength(vectorint nums1, vectorint nums2) { vectorvectorint dp(nums1.size()1,vectorint(nums2.size()1,0)); int result0; for(int i1;inums1.size();i) { for(int j1;jnums2.size();j) { if(nums1[i-1]nums2[j-1]) { dp[i][j]dp[i-1][j-1]1; } resultmax(result,dp[i][j]); } } return result; } };今日总结今天的子序列题目做起来还是比较熟悉的重复子数组稍微比较难想其实这里的更新也是一轮一轮滚动更新的重点是要理解dp数组的含义我就想不出来这个dp数组怎么设比较好。继续加油