52 第八章 动态规划
- 300.最长递增子序列
- 674. 最长连续递增序列
- 718. 最长重复子数组
详细布置
300.最长递增子序列
dp数组的定义
dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度
nums = [10,9,2,5,3,7,101,18]
相当于nums[4] ,以3为结尾(该序列长度为4),最长上升子序列的长度为2
dp[j]指的是j从(0到4-1)各个位置的最长升序子序列 + 1 的最大值。
状态转移方程
if语句的意思是:找到升序的地方.Eg:[10,9,2,5,3,7,101,18],找到5,下标为3。
if (nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
所以dp[j]+1就相当于dp[i],他们两个是一样的
max的作用不是比较大小
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
dp = [1] * len(nums)
result = 0
for i in range(1, len(nums)):
for j in range(0, i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
if dp[i]>result:
result = dp[i] #取长的子序列
return result
674. 最长连续递增序列
这个简单一点
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
#dp数组中及含义
dp = [1]*len(nums)
result = 1
#遍历顺序
for i in range(0,len(nums)-1):
#递归公式
if nums[i+1]>nums[i]:
dp[i+1] = dp[i]+1
if dp[i+1]>result:
result = dp[i+1]
return result
连续的话只用比较前面的数是不是大的,连续的话就存储,比不连续的简单
718. 最长重复子数组
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
#dp初始化
dp = [[0 for _ in range(len(nums1)+1)] for _ in range(len(nums2)+1)]
print(dp)
result =0
#初始化,都没有意义,所以都初始化为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
if dp[i][j] >result:
result = dp[i][j]
return result
稍有难度,要使用二维dp数组了