【Python算法】最长递增子序列

题目链接

方法1： 记忆化搜索

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:@cachedef dfs(i):res=0 for j in range(i):if nums[j]<nums[i]:res = max(res,dfs(j))return res+1  # 返回res表示以nums[i]结尾的LIS长度return max(dfs(i) for i in range(len(nums)))

方法2：递推

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:# 初始化:f[i] 表示以 nums[i] 结尾的最长递增子序列（LIS）的长度。f = [0]*len(nums)for i,x in enumerate(nums):for j,y in enumerate(nums[:i]): # 遍历从nums[0]到nums[i-1]if y<x:f[i] = max(f[i],f[j])f[i]+=1return max(f)