300.最长递增子序列
今天开始正式子序列系列,本题是比较简单的,感受感受一下子序列题目的思路。
视频讲解:https://www.bilibili.com/video/BV1ng411J7xP
https://programmercarl.com/0300.最长上升子序列.html
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
#以nums[i]为结尾的最长递增子序列
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i]>nums[j]:
dp[i] = max(dp[i],dp[j]+1)
max_l = 0
for lens in dp:
max_l = max(lens,max_l)
return max_l
674. 最长连续递增序列
本题相对于昨天的动态规划:300.最长递增子序列 最大的区别在于“连续”。 先尝试自己做做,感受一下区别
视频讲解:https://www.bilibili.com/video/BV1bD4y1778v
https://programmercarl.com/0674.最长连续递增序列.html
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
#以nums[i]为结尾的最长连续递增子序列
dp = [1]*len(nums)
for i in range(1,len(nums)):
if nums[i]>nums[i-1]:
dp[i]=dp[i-1]+1
max_l = 0
for lens in dp:
max_l = max(max_l,lens)
return max_l
718. 最长重复子数组
稍有难度,要使用二维dp数组了
视频讲解:https://www.bilibili.com/video/BV178411H7hV
https://programmercarl.com/0718.最长重复子数组.html
给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。
示例:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3, 2, 1] 。
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# dp[i][j] 以nums1[i]和nums2[j]结尾的公共数组的长度
dp = [[0] * len(nums2) for _ in range(len(nums1))]
for j in range(len(nums2)):
if nums2[j] == nums1[0]:
dp[0][j] = 1
for i in range(len(nums1)):
if nums1[i] == nums2[0]:
dp[i][0] = 1
for i in range(1,len(nums1)):
for j in range(1,len(nums2)):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i-1][j-1] + 1
max_l = 0
for i in range(len(nums1)):
for j in range(len(nums2)):
max_l = max(max_l,dp[i][j])
return max_l
标签:nums,max,递增,len,序列,最长,dp
From: https://www.cnblogs.com/forrestr/p/18292946