8.3 线性 DP（一）: 单串线性 DP

[giscus[bot]]

8.3 线性 DP（一）: 单串线性 DP

8.3 线性 DP（一）: 单串线性 DP --- 1. 线性动态规划简介 线性动态规划（线性 DP）：指的是将问题的阶段按线性顺序划分，并基于此进行状态转移的动态规划方法。如下图所示： 线性 DP线性 DP 即使状态有多个维度，只要每个维度的阶段划分都是线性的，也属于线性 DP。例如，背包问题、区间 DP、数位 DP 等都属于线性 DP 的范畴。 线...

https://algo.itcharge.cn/08_dynamic_programming/08_03_linear_dp_01/

[xiaos2021]

解法二，进阶的线性DP + 二分查找（数组作为可实时更新内部的单调栈 + 贪心法 + 二分查找）
解法二比解法一更高效，更重要，可用于解决后续同类问题：354，1713，2771。

import bisect
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1
        
        # tails[k] 表示长度为k+1的LIS的最小末尾元素（无闲置索引，动态扩展）
        tails = list()

        for x in nums:
            # 二分查找：在tails中找首个≥x的位置
            k = bisect.bisect_left(tails, x)

            # 若x比所有元素都大，k的结果会是当前数组长度（末尾位置索引+1）
            # x直接新增在tails数组末尾，形成新问题（LIS长度+1）
            if k == len(tails):
                tails.append(x)
            # 用较小的x更新较大的tails[k]，优化同长度LIS问题的末尾元素（变得更小）
            else:
                tails[k] = x
        
        # tails的长度即为最终LIS问题的长度
        return len(tails)

[xiaos2021]

忘说了这是第300题

[itcharge]

谢谢提供题解思路，稍后我加到文章中。