「代码随想录算法训练营」第三十七天 | 动态规划 part10
300. 最长递增子序列
题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/
文章讲解：https://programmercarl.com/0300.最长上升子序列.html
题目难度：中等
视频讲解：https://www.bilibili.com/video/BV1ng411J7xP
题目状态：有思路，但是自己能写出来还是太勉强，有些细节想不到
思路：
维护一个动规数组dp[i]，表示在遍历到数组中的第i个元素的时候，此时能找到的最长递增子序列的长度。
其更新的代码如下：if(num[i] > num[j]) dp[i] = max(dp[i], dp[j] + 1);
所以需要有两次遍历，i是整个数组的遍历，j是在当前元素前面的元素，这样就能确保dp[i]是当前最大的递增子序列的个数。
代码：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
vector<int> dp(nums.size(), 1);
int ans = 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);
}
ans = ans < dp[i] ? dp[i] : ans;
}
return ans;
}
};
674. 最长连续递增序列
题目链接：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
文章讲解：https://programmercarl.com/0674.最长连续递增序列.html
题目难度：简单
视频讲解：https://www.bilibili.com/video/BV1bD4y1778v
题目状态：这题比较简单，久违的独立通过
思路：
相较于上题，这题很简单，dp数组的更新只要依靠前一个元素就可以，若当前元素大于前一个元素，就将前一个元素的dp数组加1。
代码：
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
vector<int> dp(nums.size(), 1);
int ans = 0;
for(int i = 1; i < nums.size(); ++i) {
if(nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
ans = ans < dp[i] ? dp[i] : ans;
}
return ans;
}
};
贪心思路和代码：
维护一个变量count用来存放当前的连续递增序列的长度，如果遇到nums[i] > nums[i - 1]的情况，count就++，否则count就为1，记录count的最大值就可以了。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
int ans = 0;
int count = 1;
for(int i = 1; i < nums.size(); ++i) {
if(nums[i] > nums[i - 1]) count++;
else count = 1;
ans = ans < count ? count : ans;
}
return ans;
}
};
718. 最长重复子数组
题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
文章讲解：https://programmercarl.com/0718.最长重复子数组.html
题目难度：中等
视频讲解：https://www.bilibili.com/video/BV178411H7hV
题目状态：看题解
思路
维护一个二维动规数组d[i][j]，表示在数组1中元素为i-1和数组2中元素为j-1时的最长重复子数组的大小。
若要更新这个动规数组，我们要进行嵌套循环，第一个循环是数组1，第二个循环是数组2，其更新的条件是nums1[i - 1] = nums2[j - 1]，至于为什么是i-1和j-1，因为这样我们可以从1开始比较，避免处理i或j为0时的特殊情况。
代码
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size();
int len2 = nums2.size();
int ans = 0;
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
for(int i = 1; i <= len1; ++i) {
for(int j = 1; j <= len2; ++j) {
if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
ans = ans < dp[i][j] ? dp[i][j] : ans;
}
}
return ans;
}
};