R4-dp

目录

常规方法遇到以下序列时就会变得错误

动态规划的思路

单调栈

ps:

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:#最简单的方法n=len(nums)if n<2:return nmx=1for i in range(n):max_i=1for j in range(i+1,n):if nums[i]<nums[j]:nums[i]=nums[j]max_i+=1mx=max(mx,max_i)return mx

常规方法遇到以下序列时就会变得错误

先取了013，但0123才是最长的

观其思路，每次遍历数组后面的部分都会被遍历到，所以我们还不如从背后出发，这恰好就是

动态规划的思路

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:#dpif not nums:return 0n=len(nums)dp=[1]*nfor i in range(n):for j in range(i):if nums[i]>nums[j]:#相比我的解法关键处理的地方dp[i]=max(dp[i],dp[j]+1)return max(dp)

 

单调栈

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:#单调栈stack=[]for num in nums:if not stack or num>stack[-1]:stack.append(num)else:stack[bisect.bisect_left(stack,num)]=numreturn len(stack)

刁钻，合理

ps:

又get一个新知识