基础题目：300. 最长递增子序列
扩展题目：354. 俄罗斯套娃信封问题
一、引言：LIS 在「线性 DP」中的位置
在完整学习了：
- 打家劫舍（选 / 不选）
- 爬楼梯（排列计数）
- 背包问题（容量约束）
- 双序列线性 DP（公共子序列）
之后，最长递增子序列（LIS）是线性 DP 中最后、也是最容易“升维”的一种模型。
它的核心特征非常明确：
单序列 + 子序列 + 有序性约束
一旦理解 LIS，不仅可以解决一维问题，还可以通过排序 + 降维，解决看似更复杂的二维、分组问题。
二、354. 俄罗斯套娃信封问题
问题本质与第一直觉
每个信封用 (w, h) 表示，若：
1 | w1 < w2 且 h1 < h2 |
则信封 1 可以嵌套进信封 2。
直觉思路是：
把每个信封当成一个“元素”，求最长递增子序列
但这里存在一个关键陷阱：
题目允许任意重排信封顺序
→ 原数组顺序是无意义的
→ 直接在二维数组上做 LIS 会漏解
正确建模：二维 → 一维的关键转化
要想使用 LIS，必须满足：
只在一个维度上递增
因此需要先消除一个维度的干扰。
核心转化步骤
Step 1：排序
- 宽度
w：升序 - 高度
h：降序（当 w 相同）
1 | // 双关键字排序：宽度升序，高度降序 |
为什么 w 相同时要按 h 降序？
这是本题最容易被忽略、也是面试最常考的点。
如果：
w相同h也按升序排
那么在之后对 h 求 LIS 时，会错误地把同一宽度的信封选进子序列，违反题意（宽度必须严格递增）。
而 h 降序 的作用是：
在 LIS（严格递增）中，相同 w 的信封不可能同时被选中
问题彻底降维：只看高度 h
排序完成后：
- 宽度已经隐式满足递增约束
- 只需要在高度数组上求 严格递增 LIS
问题就完全转化为：
300. 最长递增子序列
算法复杂度分析
- 排序：
O(n log n) - LIS（贪心 + 二分）：
O(n log n)
整体复杂度：
1 | O(n log n) |
满足 n ≤ 10^5 的数据规模要求。
三、心得体会（俄罗斯套娃 → LIS）
这道题真正考察的不是 LIS 本身，而是问题转化能力：
- 是否意识到原顺序无意义
- 是否能通过排序消掉一个维度
- 是否处理了“相等元素”的边界情况
本质模型可以总结为一句话：
二维严格递增问题 = 排序 + 一维 LIS
四、线性 DP 模型全景总结
回顾整个线性 DP 学习路径，可以清晰地分为 五大模型。
打家劫舍模型（选 / 不选 + 相邻约束）
核心特征
- 枚举元素选或不选
- 相邻元素不能同时选
典型变形
- 打家劫舍 II（成环）
→ 拆成「选第一个 / 不选第一个」 - 删除并获得点数
→ 构造值域数组，转化为打家劫舍
爬楼梯模型（排列型 DP）
核心特征
- 顺序不同 = 不同方案
- 每一步选择不同“动作”
常见变形
- 最小代价爬楼梯
- 目标字符串构造方案数
- 组合总和（顺序相关）
- 分组 + 爬楼梯
背包模型（容量约束）
分类
- 01 背包（不能重复选）
- 完全背包（可以重复选）
常见问法
- 至多 / 恰好 / 至少装满
- 求最大值 / 最小值 / 方案数
重要收获
空间优化的本质：
明确当前状态依赖哪些旧状态
是否会发生状态覆盖
必要时引入
pre
双序列线性 DP
核心特征
- 操作两个序列
- 关注“公共部分”
典型问题
- 最长公共子序列（LCS）
- 最短公共超序列（SCS）
- 编辑距离
最长递增子序列（LIS）
核心特征
- 单序列
- 子序列
- 有序性约束（递增 / 非递减）
两种解法层级
| 解法 | 时间复杂度 | 适用 |
|---|---|---|
| 经典 DP | O(n²) | 理解模型 |
| 贪心 + 二分 | O(n log n) | 大规模数据 |
关键技巧
交换 dp 的“状态”与“状态值”
- 用
g[k]表示：- 长度为
k+1的递增子序列 - 其末尾元素的最小值
- 长度为
严格来说：
g不存在状态覆盖- 已不再是传统 DP
- 而是 贪心 + 有序结构 + 二分查找
相关代码
本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。