Leetcode 300. 最长递增子序列

心路历程经典的子串/子序列的DP问题这道题需要按照最后一个元素包含在子序列的角度去建模比较好做。状态以nums[i]为结尾的最长严格递增子序列的长度动作候选集每一个[0, i)之间满足比nums[i]小的元素返回值最长的子序列长度注意的点1、候选集合为多个比nums[i]小的元素不一定只是离nums[i]最近的元素。解法动态规划DP数组法classSolution:deflengthOfLIS(self,nums:List[int])-int:nlen(nums)ifn0:return0# 0和1的初始化dp[1for_inrange(n)]foriinrange(n):forjinrange(i):ifnums[i]nums[j]:dp[i]max(dp[j]1,dp[i])returnmax(dp)递归法classSolution:deflengthOfLIS(self,nums:List[int])-int:cachedefdfs(i):# 表示以nums[i]为结尾的【最长】严格递增子序列的长度ifi0:return1res1# 习惯在动态规划问题上用res不要直接return以方便一般化的记忆forjinrange(i-1,-1,-1):ifnums[j]nums[i]:# 只有在满足客观条件的情况下才能递归计算resmax(res,1dfs(j))returnres maxl0foriinrange(len(nums)):maxlmax(maxl,dfs(i))returnmaxl