阅读量:0
代码随想录–动态规划部分
day 43 动态规划第10天
文章目录
一、力扣300–最长递增子序列
代码随想录题目链接：代码随想录
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
dp数组的定义为：dp[i]代表以nums[i]结尾的 最长递增子序列的长度
那么递推公式就是if(nums[i] > nums[i-1])dp[i] = dp[i-1]+1吗
其实并不是，这样写完全是错的，举例：[1,4,7,10,299,11,13]，最长的应该是[1,4,7,10,11,13]长度为6，但是按照上面的公式为7
正确的应该是每增加一个nums，都需要遍历0到i-1的dp数组来检查
当nums[i]>nums[j]时，取dp[i]和dp[j]+1的更大值
代码如下：
class Solution { public: int lengthOfLIS(vector<int>& nums) { if (nums.size() <= 1) return nums.size(); vector<int> 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 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
限定了连续性，反而降低了题的难度，剪枝操作可以粗暴一些了
dp[i]代表以nums[i]结尾的 最长连续递增序列长度
因为必须是连续的，所以nums[i]只需要和nums[i-1]比较即可，大了就dp[i] = dp[i-1] + 1，不大的话说明这里要重开一次
最后取dp最大值输出即可
class Solution { public: int findLengthOfLCIS(vector<int>& nums) { int result = 0; if(!nums.size()) return 0; if(nums.size() == 1) return 1; vector<int> 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 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
这个题要构建二维的dp数组
dp[i][j]代表：以nums1[i-1]和nums[j-1]结尾的 最长公共子数组的长度
这样写的话，递推公式非常简单，就是判断nums1[i]==nums2[j]，如果一样的话，子数组长度加一，也就是d[i+1][j+1] = dp[i][j]+1
遍历的话就无所谓了，只要能保证 n 2 n^2 n2的组合全部遍历过就行，外循环遍历nums1，内循环遍历num2就可以
至于初始化，假设完全没有重复子数组的话，是不是应该返回0，那么dp全部初始化为0就可以了
代码如下：
class Solution { public: int findLength(vector<int>& nums1, vector<int>& nums2) { vector<vector<int>> dp (nums1.size() + 1, vector<int>(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; } }; 