算法学习（一） 动态规划-习题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)
        # 牌堆数初始化为0
        piles = 0

        for poker in nums:
            # 二分查找左边界
            left,right = 0,piles
            while left < right:
                mid = (left+right) // 2
                if top[mid] < poker:
                    left = mid + 1
                else:
                    right = mid

            # 若没有找到合适的牌堆，新建一个牌堆
            if left == piles:
                piles += 1
        
            # 把这张牌放在对应的牌堆顶部
            top[left] = poker

        return piles