代码随想录算法训练营Day52 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组 | Python | 个人记录向

注：Day51休息。

300.最长递增子序列

代码随想录：300.最长递增子序列
Leetcode：300.最长递增子序列

做题

无思路。

看文章

动规五部曲：

1. dp[i]的定义。dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。
2. 状态转移方程。if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)。
3. dp[i]的初始化。至少为1。
4. 确定遍历顺序。遍历i的循环在外层，遍历j则在内层。
5. 举例推导dp数组。

看完思路后自己实现。这里有个特殊点，最后要return max(dp)，因为dp数组代表的是以 nums[i] 为结尾的最长递增子序列的长度，故需要返回最大值。

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:size = len(nums)dp = [1] * sizefor i in range(size):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)

时间复杂度: O(n^2)
空间复杂度: O(n)

674. 最长连续递增序列

代码随想录：674. 最长连续递增序列
Leetcode：674. 最长连续递增序列

做题

无思路。

看文章

动规五部曲：

1. dp[i]的定义。dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
2. 状态转移方程。如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。即：dp[i] = dp[i - 1] + 1。
3. dp[i]的初始化。至少为1。
4. 确定遍历顺序。从前往后，单层遍历
5. 举例推导dp数组。

class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:size = len(nums)if size == 1:return 1dp = [1] * sizefor i in range(1, size):if nums[i] > nums[i-1]:dp[i] = dp[i-1] + 1return max(dp)

时间复杂度：O(n)
空间复杂度：O(n)

718. 最长重复子数组

代码随想录：718. 最长重复子数组
Leetcode：718. 最长重复子数组

做题

无思路。

看文章

动规五部曲：

1. dp数组的定义。dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。（i-1是为了方便初始化）
2. 状态转移方程。根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来，即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1。根据递推公式可以看出，遍历 i 和 j 要从1开始！
3. dp[i]的初始化。dp[i][0] 和dp[0][j]初始化为0。
4. 确定遍历顺序。
5. 举例推导dp数组。

class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:dp = [[0] * (len(nums2)+1) for _ in range(len(nums1)+1)]res = 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] + 1res = max(res, dp[i][j])return res

时间复杂度：O(n × m)，n 为A长度，m为B长度
空间复杂度：O(n × m)

以往忽略的知识点小结

• 子序列的dp数组定义：以 i 结尾的最长xxx子序列

个人体会

完成时间：1h50min。
心得：新题型，用动态规划处理子序列问题。

​