代码随想录算法训练营第52天|300.最长递增子序列,674. 最长连续递增序列,718. 最长重复子数组
- 300.最长递增子序列
- 674. 最长连续递增序列
- 718. 最长重复子数组
300.最长递增子序列
题目链接:300.最长递增子序列,难度:中等
【实现代码】
//动态规划
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int result = 1;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;}
};//动态规划+二分查找
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> tail;tail.push_back(nums[0]);for (int i = 1; i < nums.size(); i++) {if (nums[i] > tail.back()) {tail.push_back(nums[i]);} else {int left = 0;int right = tail.size() - 1;while (left <= right) {int mid = (left + right) >> 1;if (tail[mid] >= nums[i]) {right = mid - 1;} else {left = mid + 1;}}if (left < tail.size()) {tail[left] = nums[i];} }}return tail.size();}
};
【解题思路】
动规五部曲:
- dp[i]的定义:dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
- 状态转移方程:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
- dp[i]的初始化:每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.
- 确定遍历顺序:dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来,那么遍历i一定是从前向后遍历。
- 举例推导dp数组
动态规划+二分查找题解
674. 最长连续递增序列
题目链接:674. 最长连续递增序列,难度:简单
【实现代码】
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int result = 1;for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;result = result > dp[i] ? result : dp[i];}}return result;}
};
【解题思路】
动规五部曲:
- dp[i]的定义:dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]。
- 状态转移方程:if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
- dp[i]的初始化:每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.
- 确定遍历顺序:dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来,那么遍历i一定是从前向后遍历。
- 举例推导dp数组
718. 最长重复子数组
题目链接:718. 最长重复子数组,难度:中等
【实现代码】
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 (result < dp[i][j]) {result = dp[i][j];}}}return result;}
};
【解题思路】
动规五部曲:
- dp[i]的定义:dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。 (特别注意: “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 )
- 状态转移方程:当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
- dp[i]的初始化:dp[0][0]初始为0
- 确定遍历顺序:外层for循环遍历A,内层for循环遍历B。在遍历的时候顺便把dp[i][j]的最大值记录下来。
- 举例推导dp数组