Leetcode 300. 最长递增子序列

心路历程：

经典的子串/子序列的DP问题，这道题需要按照最后一个元素包含在子序列的角度去建模比较好做。

状态：以nums[i]为结尾的最长严格递增子序列的长度
动作候选集：每一个[0, i)之间满足比nums[i]小的元素
返回值：最长的子序列长度

注意的点：

1、候选集合为多个比nums[i]小的元素，不一定只是离nums[i]最近的元素。

解法：动态规划

DP数组法

classSolution:deflengthOfLIS(self,nums:List[int])->int:n=len(nums)ifn==0: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]为结尾的【最长】严格递增子序列的长度ifi==0:return1res=1# 习惯在动态规划问题上用res不要直接return，以方便一般化的记忆forjinrange(i-1,-1,-1):ifnums[j]<nums[i]:# 只有在满足客观条件的情况下，才能递归计算res=max(res,1+dfs(j))returnres maxl=0foriinrange(len(nums)):maxl=max(maxl,dfs(i))returnmaxl