300.最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence/
代码随想录
https://programmercarl.com/0300.最长上升子序列.html
674.最长连续递增序列
https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/
代码随想录
https://programmercarl.com/0674.最长连续递增序列.html#算法公开课
718.最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
代码随想录
https://programmercarl.com/0718.最长重复子数组.html#其他语言版本
300.最长递增子序列
题解
- dp数组定义：dp[i]到以nums[i]为结尾的最长递增子序列的长度；
- 递推序列：
- j遍历i之前每一个元素：dp[i] = max(dp[j]+1,dp[i])
- 初始化：
- dp = [1]*n
- 遍历顺序
- i：从小到大遍历；依赖前面计算过的结果；
- j：前后都可以；元素完整即可；
点击查看代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if len(nums)==1:
return 1
if len(nums)==0:
return 0
dp = [1]*len(nums)
res = 0
for i in range(1,len(nums)):
for j in range(0,i):
if nums[j]<nums[i]:
dp[i] = max(dp[i],dp[j]+1)
if dp[i]>res:
res = dp[i]
return res
674.最长连续递增序列
题解
- dp数组定义：变成连续递增的最长递增子序列
- 递推公式变了：只和i-1有关
- dp[i] = dp[i-1]+1
点击查看代码
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if len(nums)==1:
return 1
if len(nums)==0:
return 0
dp = [1]*len(nums)
res = 0
for i in range(1,len(nums)):
if nums[i]>nums[i-1]:
dp[i] = dp[i-1]+1
if dp[i]>res:
res = dp[i]
# print(dp)
return res
718. 最长重复子数组
题解
- 递推公式：dp[i][j] = dp[i-1][j-1]+1
- 不需要比较dp[i-1][j]和dp[i][j-1]
点击查看代码
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m = len(nums1)
n = len(nums2)
## dp[i][j] 前i个j个元素中相同的元素有几个；
dp = [[0]*(n+1) for _ in range(m+1)]
## 不需要专门遍历某一行 直接从第1行开始就可以
res = 0
## 统一扩大一行
for i in range(1,m+1):
for j in range(1,n+1):
if nums1[i-1]==nums2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
if dp[i][j]>res:
res = dp[i][j]
return res