学习资料：https://programmercarl.com/0300.最长上升子序列.html#算法公开课
动态规划系列之子序列
学习记录
300.最长递增子序列（长度最少为1；dp[i]代表到i为止的最长子序列的长度；i的值根据i之前比如j的值来判断；每个地方都有可能获得最长长度）
点击查看代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 动态规划，dp[i]代表以i或i以前的下标作为结尾时的递增子序列的最长长度
if len(nums) <= 1:
return len(nums)
# 构造dp数组
dp = [1]*(len(nums))
# # 初始化
# dp[0] = 1 # 一个数则递增子序列长度为1
# 保存一下最长长度
result = 1
# 开始遍历
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) # 如果是前面某个数达到最长长度那么再加个i就是+1
result = max(result, dp[i])
return result
674.最长连续递增序列（与300题相比，因为连续就把j的都换成i-1就好了）
点击查看代码
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if len(nums)<=1:
return len(nums)
dp = [1]*len(nums)
result = 1
# 要找连续递增子序列，就只需要考虑i与i-1，而不用来一个j了
for i in range(1, len(nums)):
if nums[i]>nums[i-1]:
dp[i] = max(dp[i], dp[i-1]+1)
result = max(result, dp[i])
return result
718.最长重复子数组（与674题相比，变成二维dp数组；当前一脚标的值相等，那两者都向后遍历，知道两者值不相等为止，那这段就是公共子数组长度）
点击查看代码
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# 构造dp[i][j]代表num1以i-1为结尾,num2中以j-1为结尾的最长重复连续子序列
dp = [[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
# 收集最大值
result = 0
# 开始遍历
for i in range(1, len(nums1)+1):
for j in range(1, len(nums2)+1):
if nums1[i-1]==nums2[j-1]:
# 当前最长公共子数组长度为前一位置上的长度加1
dp[i][j] = dp[i-1][j-1] + 1 # 同理于最长连续递增子数列
if dp[i][j] > result:
result = dp[i][j]
return result
PS:今天学的最早，但是没学懂，特别是第一天，怎么判断最长递增子序列
又是小雨的一天，突然发现在一个空旷的，只有灯带来光明且充满噪音的地方是难受的，但是说不定会习惯呢
早饭吃的好，一天干劲儿真不少
今天收到两个拒信，果然不好的预感一般很准。不过又有一些新的想去的地方出现，希望能把握住