动态规划 leetcode_300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组
昨天结束了买卖股票系列,今天开始正式子序列系列!
300.最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
- dp[i]的定义
本题中,正确定义dp数组的含义十分重要。
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度 - 状态转移方程
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值。 - dp[i]的初始化
每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1. - 确定遍历顺序
dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来,那么遍历i一定是从前向后遍历。 - 举例推导dp数组
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums) < 2: return len(nums)dp = [1] * len(nums)res = 0for i in range(1,len(nums)):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)if dp[i] > res: res = dp[i] #取长的子序列return res
本题最关键的是要想到dp[i]由哪些状态可以推出来,并取最大值,那么很自然就能想到递推公式:dp[i] = max(dp[i], dp[j] + 1);
674. 最长连续递增序列
给定一个未经排序的整数数组,找到最长且连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
- 确定dp数组(dp table)以及下标的含义
dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]。
注意这里的定义,一定是以下标i为结尾,并不是说一定以下标0为起始位置。 - 确定递推公式
如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。
即:dp[i] = dp[i - 1] + 1;
*注意这里就体现出和动态规划:300.最长递增子序列的区别!
因为本题要求连续递增子序列,所以就只要比较nums[i]与nums[i - 1],而不用去比较nums[j]与nums[i] (j是在0到i之间遍历)。
既然不用j了,那么也不用两层for循环,本题一层for循环就行,比较nums[i] 和 nums[i - 1]。 - dp数组如何初始化
以下标i为结尾的连续递增的子序列长度最少也应该是1,即就是nums[i]这一个元素。
所以dp[i]应该初始1; - 确定遍历顺序
从递推公式上可以看出, dp[i + 1]依赖dp[i],所以一定是从前向后遍历。 - 举例推导dp数组
class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:if len(nums) < 2: return len(nums)dp = [1] * len(nums)res = 1for i in range(1,len(nums)):if nums[i] > nums[i-1]:dp[i] = dp[i-1] + 1res = max(res, dp[i])return res
贪心:
class Solution:def findLengthOfLCIS(self, nums: List[int]) -> int:if len(nums) < 2: return len(nums)count = 1res = 1for i in range(1,len(nums)):if nums[i] > nums[i-1]:count += 1else:count = 1res = max(count, res)return res
718. 最长重复子数组
给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。
- 确定dp数组(dp table)以及下标的含义
dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。 (特别注意: “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 )
dp[i][j]的定义也就决定着,我们在遍历dp[i][j]的时候i 和 j都要从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数组如何初始化
根据dp[i][j]的定义,dp[i][0] 和dp[0][j]其实都是没有意义的!
但dp[i][0] 和dp[0][j]要初始值,因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
所以dp[i][0] 和dp[0][j]初始化为0。
举个例子A[0]如果和B[0]相同的话,dp[1][1] = dp[0][0] + 1,只有dp[0][0]初始为0,正好符合递推公式逐步累加起来。 - 确定遍历顺序
外层for循环遍历A,内层for循环遍历B。 - 举例推导dp数组
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:dp = [[0 for _ in range(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
一开始想不到思路,看完题解又是恍然大悟的感觉,需要细细去品,把dp打印下来去看!