郴州建设网站哪家好,wordpress代码实现下载,单页设计是什么意思,网站开发工资多少稳定么心路历程#xff1a;
经典的子串/子序列的DP问题#xff0c;这道题需要按照最后一个元素包含在子序列的角度去建模比较好做。
状态#xff1a;以nums[i]为结尾的最长严格递增子序列的长度 动作候选集#xff1a;每一个[0, i)之间满足比nums[i]小的元素 返回值#xff1a…
心路历程
经典的子串/子序列的DP问题这道题需要按照最后一个元素包含在子序列的角度去建模比较好做。
状态以nums[i]为结尾的最长严格递增子序列的长度 动作候选集每一个[0, i)之间满足比nums[i]小的元素 返回值最长的子序列长度
注意的点
1、候选集合为多个比nums[i]小的元素不一定只是离nums[i]最近的元素。
解法动态规划
class Solution:def lengthOfLIS(self, nums: List[int]) - int:cachedef dfs(i): # 表示以nums[i]为结尾的【最长】严格递增子序列的长度if i 0: return 1res 1 # 习惯在动态规划问题上用res不要直接return以方便一般化的记忆for j in range(i-1, -1, -1):if nums[j] nums[i]: # 只有在满足客观条件的情况下才能递归计算res max(res, 1 dfs(j))return resmaxl 0for i in range(len(nums)):maxl max(maxl, dfs(i))return maxl
