代码随想录算法训练营day43 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
碎碎念：
参考：代码随想录
300.最长递增子序列
题目链接
300.最长递增子序列
思想
动态规划五部曲：
- 确定dp数组以及下标的含义：dp[i]，以nums[i]为结尾的最长递增子序列的长度，结果要返回dp数组中的最大值。
- 确定递推公式：如果nums[i] > nums[j]: dp[i] =max(dp[j]+1, dp[i])。
- dp数组的初始化：dp[0] = 1，dp[1]=1
- 确定遍历顺序：for循环，i从小到大遍历，j从小到大去遍历或者从大到小遍历都可以，本题解写的时从小到大去遍历。
- 打印dp数组：主要用来debug。
题解
// cpp
class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() == 1) return nums.size();vector<int> dp(nums.size(), 1);dp[0] = 1;dp[1] = 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[j] + 1, dp[i]);}if (dp[i] > result)result = dp[i];}return result;}
};
# python
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums) <= 1:return len(nums)dp = [1] * len(nums)result = 0for i in range(1, len(nums)):for j in range(0, i):if nums[i] > nums[j]:dp[i] = max(dp[j] + 1, dp[i])if result < dp[i]:result = dp[i]return result反思
注意对len(nums) <= 1条件的处理。
674. 最长连续递增序列
题目链接
674. 最长连续递增序列
思想
本题和上一题最大的区别在于“连续”。体现在代码里就是递推公式前判断一下当前元素和上一个元素的大小关系，上一题的这部分要判断当前元素和之前所有元素的大小关系。
动态规划五部曲：
- 确定dp数组以及下标的含义：dp[i]，以nums[i]为结尾的最长连续递增子序列的长度，结果要返回dp数组中的最大值。
- 确定递推公式：如果nums[i] > nums[i-1]: dp[i] = dp[i - 1] + 1
- dp数组的初始化：dp[0] = 1，dp[1]=1
- 确定遍历顺序：for循环，i从小到大遍历。
- 打印dp数组：主要用来debug。
题解
// cpp
class Solution {
public:int findLengthOfLCIS(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++) {if (nums[i - 1] < nums[i])dp[i] = dp[i - 1] + 1;if (dp[i] > result)result = dp[i];}return result;}
};
# python
class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:if len(nums) <= 1:return len(nums)dp = [1] * len(nums)result = 0for i in range(1, len(nums)):if nums[i - 1] < nums[i]:dp[i] = dp[i - 1] + 1if result < dp[i]:result = dp[i]return result
反思
718. 最长重复子数组
题目链接
718. 最长重复子数组
思想
子数组就是连续的子序列。
动态规划五部曲：
- 确定dp数组以及下标的含义：dp[i][j]，以i-1为结尾的nums1和以j-1为结尾的nums2，这两个数组的最长重复子数组的长度。结果要返回dp数组中的最大值。
- 确定递推公式：如果nums1[i-1]==nums2[j-1]，dp[i][j] = dp[i-1][j-1]+1
- dp数组的初始化：dp数组的第一行和第一列都没有意义，初始化为0
- 确定遍历顺序：两层for循环，遍历nums1和nums2，先遍历谁都可以
- 打印dp数组：主要用来debug。注意范围是i<nums1.size()，而不是nums1.size()-1，这点是根据我们对dp数组的定义得出的。
题解
// cpp
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;}
};
# python
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:# 这里注意别把nums1和nums2搞反了dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]result = 0for i in range(1, len(nums1) + 1):for j in range(1, len(nums2) + 1):if nums1[i - 1] == nums2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1if result < dp[i][j]:result = dp[i][j]return result反思
本题也可以做状态压缩。
dp[i][j]，以i-1为结尾的nums1和以j-1为结尾的nums2，这两个数组的最长重复子数组的长度。
这样定义递推公式的时候初始化更方便。