Pattern 18 · Subsequence DP (LIS)

18 子序列 DP LIS 两解法：O(n²) DP 与「耐心排序 + 二分」

面试频率 中题目 3 道模板 2 个⭐认脸 1 道
§1 Mental Model 一句话心智模型

先记住这一句

LIS 的状态定义是「以 i 结尾的最长上升子序列」——「以 i 结尾」这四个字是全章的钥匙。O(n²) 是两层循环回头看；O(n log n) 是用一个 tails 数组做二分。

面试的标准打法：先讲 O(n²) 的状态定义与转移，再说「还能用耐心排序 + 二分做到 O(n log n)」，然后写后者。只写快的说不清来龙去脉，只写慢的显得没准备。

tails 那个数组必须讲清楚一件事：tails[k] 是「长度为 k+1 的上升子序列中最小的结尾」，它本身通常不是任何一条真实的 LIS——只有它的长度是对的。面试官很爱追问这一点，答不上来会被认为是背的。

§2 Recognition Signals 识别信号

看到什么，想到本章

题面出现…想到
「最长上升 / 递增子序列」（不要求连续）LIS（模板 A 或 B）
「最长数对链 / 俄罗斯套娃信封」先排序，再对另一个维度求 LIS
「最长可整除子集 / 最长字符串链」排序后把「能否接上」换成整除 / 差一个字母
「有多少个最长上升子序列」再开一个 count 数组（673）
「最少用几个不升序列覆盖」Dilworth 定理，答案等于 LIS 长度
「子序列」+「最长 / 最多」且只有一个序列本章；两个序列是第 17 章的 LCS
分流条件 · 决策树同源

连续才是滑动窗口（第 03 章）或前缀和（第 13 章），子序列（可以跳着取）才是本章——这两个字是最关键的分流点。只求「最大和的连续子数组」是 Kadane（第 15 章）。两个序列之间的公共子序列（LCS）是第 17 章的双序列表；本章只有一个序列，转移要回头看所有更早的元素。

§3 Template 模板代码

可默写的那几行

■ 【骨架】 不变，闭着眼默写　■ 【插槽】 随题变化，写题前先问自己填什么

模板 A · O(n²) LIS先能讲清它，再谈优化
def length_of_lis(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)                    # 【骨架】dp[i] = 「以 i 结尾」的最长长度
    for i in range(len(nums)):              # 【骨架】
        for j in range(i):                  # 【骨架】回头看所有更早的元素
            if nums[j] < nums[i]:           # 【插槽】能否接在 j 后面:严格上升 / 非降 / 整除
                dp[i] = max(dp[i], dp[j] + 1)   # 【插槽】接上之后怎么更新
    return max(dp)                          # 【插槽】答案在所有结尾里取最大,不是 dp[-1]
默写口诀：以 i 结尾、回头看 j、能接就接、答案取 max(dp)。「以 i 结尾」决定了答案是 max(dp) 而不是 dp[-1]。
模板 B · 耐心排序 + 二分O(n log n)，面试主推
import bisect

def length_of_lis_fast(nums):
    tails = []                              # 【骨架】tails[k] = 长度为 k+1 的上升子序列的最小结尾
    for x in nums:                          # 【骨架】
        i = bisect.bisect_left(tails, x)    # 【插槽】bisect_left 严格上升;bisect_right 允许相等
        if i == len(tails):                 # 【骨架】比所有结尾都大 -> 接出更长的一条
            tails.append(x)
        else:
            tails[i] = x                    # 【骨架】否则用它替换掉那个更大的结尾
    return len(tails)                       # 【插槽】只有长度可信,tails 本身不是某条 LIS
严格上升用 bisect_left（相等的会被替换掉），允许相等用 bisect_right。一个字母的差别，354 就靠它。
§4 Problems 题目分层

从建直觉到扭模板

标准模板直接套1 道
  • 300 Longest Increasing SubsequenceMedium
    本章的母题。两种解法都要会：先讲 O(n²) 的状态定义，再写 O(n log n)。本章刻意没有热身题——300 之前没有更简单的 LIS 可讲。
变体模板要扭，坑的来源2 道
  • 673 Number of Longest Increasing SubsequenceMedium
    在模板 A 上再挂一个 cnt 数组，分「发现更长」（方案数继承）和「等长的另一条路」（方案数累加）两种情况。两种情况写反是唯一的坑，模板测试里留了 [2,2,2,2,2] 这条断言。
  • 354 Russian Doll Envelopes⭐ 认脸Hard
    ⭐认脸。宽升序、宽相同时高降序，然后对高求 LIS。高要降序是为了让同宽的信封无法互相嵌套——说得出这一句就够。
§5 Pitfalls & Self-check 常见翻车点 + 自测

会写不等于不翻车

  1. 答案写成 dp[-1]——状态是「以 i 结尾」，最优的那条未必在末尾结束。必须 max(dp)。
  2. 把 tails 当成 LIS 本身——tails 只保证长度正确，内容通常不是任何一条真实的上升子序列。要还原具体序列得额外记前驱下标。
  3. bisect_left 和 bisect_right 用反——严格上升用 bisect_left；写成 bisect_right，[7,7,7,7] 会返回 4 而不是 1。
  4. 354 排序时高也用升序——宽相同的信封若按高升序排，它们之间会被当成可嵌套，答案偏大。必须高降序。
  5. 把「连续子数组」当子序列做——LIS 允许跳着取，[10, 9, 2, 5, 3, 7] 的答案是 3（2, 3, 7）而不是相邻的那段。读题时先确认要不要连续，见 §2 分流条件。

自测 · 30 秒识别模式

30 秒识别Q1 · 368 Largest Divisible Subset：从一组互不相同的正整数里，选出最大的子集，使其中任意两个数都能互相整除。你的第一反应是哪个模式？

看答案

LIS 变体（模板 A）。先排序，把「能否接在 j 后面」的条件从 nums[j] < nums[i] 换成 nums[i] % nums[j] == 0，骨架一行没动。要返回子集本身，所以还得记前驱下标。

30 秒识别Q2 · 1048 Longest String Chain：若在字符串 A 中插入一个字母能得到 B，则 A 是 B 的前身。求最长的词链长度。你的第一反应是哪个模式？

看答案

LIS 变体。按长度排序后，「能否接上」变成「删掉一个字母是否相等」。用哈希表按「前身」直接转移比两层循环更快，但状态定义还是「以某个词结尾的最长链」。

30 秒识别Q3 · 53 Maximum Subarray：求连续子数组的最大和。你的第一反应是哪个模式？

看答案

贪心 / Kadane，不是本章——「连续」两个字直接排除了子序列 DP。LIS 要回头看所有更早的元素（O(n²)），而连续的只需要看前一个（cur = max(x, cur + x)，O(n)）。见 §2 分流条件与第 15 章。

每章自测都会混入恰好一道非本章题，防止「读哪章选哪章」的条件反射；题面也一律取自本章未收录的题，避免凭记忆而非凭信号作答。