代码随想录算法训练营Day52 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组 | Python | 个人记录向
注：Day51休息。
300.最长递增子序列
代码随想录：300.最长递增子序列
Leetcode：300.最长递增子序列
做题
无思路。
看文章
动规五部曲：
- dp[i]的定义。dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度。
- 状态转移方程。if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)。
- dp[i]的初始化。至少为1。
- 确定遍历顺序。遍历i的循环在外层，遍历j则在内层。
- 举例推导dp数组。
看完思路后自己实现。这里有个特殊点，最后要return max(dp)，因为dp数组代表的是以 nums[i] 为结尾的最长递增子序列的长度，故需要返回最大值。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
size = len(nums)
dp = [1] * size
for 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. 最长连续递增序列
做题
无思路。
看文章
动规五部曲：
- dp[i]的定义。dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
- 状态转移方程。如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。即：dp[i] = dp[i - 1] + 1。
- dp[i]的初始化。至少为1。
- 确定遍历顺序。从前往后，单层遍历
- 举例推导dp数组。
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
size = len(nums)
if size == 1:
return 1
dp = [1] * size
for i in range(1, size):
if nums[i] > nums[i-1]:
dp[i] = dp[i-1] + 1
return max(dp)
时间复杂度：O(n)
空间复杂度：O(n)
718. 最长重复子数组
代码随想录：718. 最长重复子数组
Leetcode：718. 最长重复子数组
做题
无思路。
看文章
动规五部曲：
- dp数组的定义。dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。（i-1是为了方便初始化）
- 状态转移方程。根据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开始！
- dp[i]的初始化。dp[i][0] 和dp[0][j]初始化为0。
- 确定遍历顺序。
- 举例推导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 = 0
for 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] + 1
res = max(res, dp[i][j])
return res
时间复杂度：O(n × m)，n 为A长度，m为B长度
空间复杂度：O(n × m)
以往忽略的知识点小结
- 子序列的dp数组定义：以 i 结尾的最长xxx子序列
个人体会
完成时间：1h50min。
心得：新题型，用动态规划处理子序列问题。