2025-2-7-算法学习（一） 动态规划-习题1 300.最长递增子序列

算法学习（一） 动态规划-习题1 300.最长递增子序列

习题链接：
https://leetcode.cn/problems/longest-increasing-subsequence/description/

  开始快速的跟着 labuladong算法小抄 开始把算法过一遍，语言是 python3 ，正好复习一下，认认真真地系统学一遍，不再糊弄自己了，加油。

（1）题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

（2）举例：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

（3）提示

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4
• 将算法的时间复杂度降低到 O(n log(n)) - 二分查找，动态规划复杂度为 O(n^2)

（4）分析

• 动态规划的题目，关键是搞明白把 最优问题 转变为 最优子问题，这样就可以写出 dp 数组

（5）动态规划代码：

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:# 动态规划 复杂度O(n^2)dp = [1] * len(nums)# 外层循环，控制总的dp数组长度for i in range(len(nums)):# 内层循环，控制每一位得到的最优解for j in range(i):# 当前元素大于之前的元素，进行判断比较，确定是否更新if (nums[j] < nums[i]):# 这一步的更新很有趣哦！dp[i] = max(dp[i],dp[j]+1)return max(dp)

（6）二分查找代码

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:# 二分法，复杂度 O(n log n) 思路感觉和动态差别不大，但思维巧妙# 初始化 top 列表，存储每个牌堆顶部的扑克牌top = [0]*len(nums)# 牌堆数初始化为0piles = 0for poker in nums:# 二分查找左边界left,right = 0,pileswhile left < right:mid = (left+right) // 2if top[mid] < poker:left = mid + 1else:right = mid# 若没有找到合适的牌堆，新建一个牌堆if left == piles:piles += 1# 把这张牌放在对应的牌堆顶部top[left] = pokerreturn piles