算法►动态规划

线性 DP · 最长递增子序列（LIS）专题总结

基础题目：300. 最长递增子序列

扩展题目：

  • 将三个组排序
  • 找出到每个位置为止最长的有效障碍赛跑路线
  • 得到山型数组的最少删除次数
  • 使数组 K 递增的最少操作次数

一、概述：为什么 LIS 是一种“新的线性 DP”

这两天的题目有一个非常鲜明的共同点：

都是「单数组 + 子序列 + 有序性」问题

它们与之前接触的模型（如 0/1 背包、完全背包、双序列 DP）有本质区别：

  • 不是选容量 / 次数
  • 不是两个序列之间的匹配
  • 而是：在保持原相对顺序的前提下，选出一个“有序的子序列”

这类问题的核心关键词是：

  • 子序列（Subsequence）
  • 递增 / 不降（有序性约束）
  • 最长 / 最少删除（等价转化）

而这一整类问题，几乎都可以归约到一个经典母题：

最长递增子序列（LIS）

二、300. 最长递增子序列（LIS）

从回溯到 O(n²) 线性 DP

思维起点：子序列 = 子集的一种

LIS 本质是一个「选或不选」的问题，可以有两种回溯视角：

  • 枚举元素选不选
    → 需要额外维护「上一个选了谁」
  • 枚举答案以谁结尾（更适合 DP）
    → 只关心：以 nums[i] 结尾的 LIS 最长是多少

状态定义

1
dp[i]：以 nums[i] 结尾的最长严格递增子序列长度

状态转移

1
dp[i] = max(dp[j] + 1)  (j < i 且 nums[j] < nums[i])

复杂度

  • 状态数：n
  • 转移代价：n
  • 时间复杂度：O(n²)

考虑优化时间复杂度。

贪心 + 二分：从 O(n²) 到 O(n log n)

当 n 上到 10⁵ 时，O(n²) 就不够用了，需要进一步优化。

核心技巧只有一句话：

将 dp 的「状态」和「状态值」进行交

关键构造：g 数组

我们不再显式记录「每个位置的 LIS 长度」，而是维护一个数组：

1
g[k]：长度为 k+1 的递增子序列，其末尾元素的最小可能值

它有两个重要性质：

  • g 始终是单调递增的
  • g.size() 就是当前 LIS 的长度

遍历过程（贪心本质）

对每个元素 x = nums[i]：

  1. 在 g 中二分查找：
    • 严格递增 LIS：找第一个 >= x 的位置
  2. 分两种情况：
    • 找不到（位置 == g.size）
      → 说明可以扩展长度，g.add(x)
    • 找到了
      → 用 x 替换该位置，g[pos] = x

为什么可以替换+为什么要替换

因为：

  • 我们只关心 在固定长度下，末尾元素越小越好
  • 更小的末尾元素，能给后续元素留下更大的扩展空间

这就是贪心正确性的核心。

时间复杂度：O(n log n)

三、LIS 的“模型迁移”：扩展题统一视角

2826. 将三个组排序

核心转化：

  • 不要求严格递增
  • 只要求 非递减子序列

问题等价于：

1
最少操作数 = n - 最长非递减子序列长度

实现细节：

  • 二分时找 第一个 > x 的位置

1964. 有效障碍赛跑路线

题目要求的是：

到每个位置为止的最长非递减子序列长度

关键点：

  • g 数组的维护方式不变
  • 每次插入 / 替换后：当前 g.size() 就是答案，因为遍历nums的过程，每个数都对应一次操作。

本质是 LIS 贪心过程的“在线版本”

1671. 得到山型数组的最少删除次数

标准「山型数组」模型：

  • 枚举 i 作为峰顶
  • 左边：最长严格递增子序列
  • 右边：最长严格递减子序列

处理技巧：

  • 右侧「严格递减」
    → 倒序遍历，等价于再做一次 LIS

答案计算：

1
n - (len_left + len_right - 1)

注意边界：

  • 峰顶左右必须至少有一个元素 → len_left >= 2 && len_right >= 2

2111. 使数组 K 递增的最少操作次数

核心拆解：

  1. 按下标 i % k 分成 k 组
  2. 每一组 互不影响
  3. 对每一组：
    • 求最长非递减子序列长度

最终答案：

1
总长度 - 各组 LNDS 之和

这是一个非常经典的：

“全局问题 → 独立子问题 → LIS 统一求解”

四、方法论总结

子序列 + 最少操作 = 最长子序列

只要题目满足：

  • 只能删除 / 修改
  • 不改变相对顺序

几乎都可以转化为：

1
最少操作 = n - 最长满足条件的子序列长度

严格递增 vs 非递减（二分差异）

子序列类型 二分查找条件
严格递增 LIS 找第一个 >= x
非递减 LNDS 找第一个 > x

这是 LIS 题中最容易写错的点

为什么 LIS 属于线性 DP

  • 本质仍是 DP
  • 只是通过：
    • 贪心
    • 有序结构
    • 二分查找
  • 将状态转移从 O(n) 优化成 O(log n)

这个优化的关键技巧只有一句话：

交换 dp 的“状态”和“状态值”

五、总结

300. 最长递增子序列（LIS）是一个“母题”：

  • 它不是一题，而是一整类题型的统一入口

  • 一旦 LIS 的 O(n²) 与 O(n log n) 两套思路真正吃透：

    • 山型数组

    • 非递减序列

    • 分组 LIS

    • 最少删除 / 修改问题

都可以自然转化、快速识别

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。