3. 分治 vs 贪心 vs DP: 什么是"最优子问题分解"
一句话
分治 / 贪心 / DP 表面上是三种范式, 仔细看它们其实是"怎么把原问题分解成子问题"的三个约束等级: 从几乎不设限 (分治) 到要求子问题可枚举、按序求解且共享结果 (DP). 理解三种范式的"分解自由度"梯度, 拿到新题就能按顺序机械地排查.
思想链
工程问题: 拿到一道新题, 先试分治、贪心还是 DP?
└─► 第一问: 子问题怎么分解?
└─► 子问题互不重叠, 合并即可 ──────────► 分治
└─► 局部最优可证明等于全局最优 ─────────► 贪心
└─► 子问题大量重叠, 需要共享解 ─────────► DP
└─► 三者共用同一块地基: 最优子结构
└─► 分治: 只要组合函数保持一致
└─► 贪心: 再加无后效性 + 贪心选择性质
└─► DP: 再加子问题空间有限、可枚举
└─► 范式之间可以互相退化
└─► DP 表里的冗余信息被剪掉 → 变成贪心 (LIS 的 tails 二分)
分级: 从"分解自由度"看三种范式
分治: 任意分解 (递归不考虑子问题之间的依赖), 每个子问题解一次
贪心: 每步只看眼前局部最优, 不回退, 不组合
DP: 列出全部子问题, 按依赖序求解, 子问题之间共享中间结果
三者都是"分解 + 合并", 但对分解形态的约束依次更紧:
- 分治: 对分解形态无要求, 子问题彼此独立;
- 贪心: 要求无后效 + 局部最优即全局最优 (贪心选择性质);
- DP: 子问题之间存在重叠, 必须显式表达依赖以便 memo 化.
数学表达
考虑原问题 P(x). 三种范式都把 P 分解为子问题 P(x_i):
分治: P(x) = combine(P(x1), P(x2)). 子问题彼此独立.
贪心: P(x) = choice(x_k) + P(rest), 其中 x_k 是当前可证局部最优的选择. 选完直接剪掉, 不回头.
DP: P(x) = opt_i { P(x_i') + cost }. 子问题之间是重叠的 —— 多个 P(x) 共享同一批 P(x_i'). 用一张表按拓扑序求解所有子问题, 中间结果只算一次.
三种范式的共同源头
每种范式都假设最优子结构:
P(x) 的最优解由其子问题 P(x_i) 的最优解组合而成.
只要组合时用的是 max / min 这类保序运算,
"子问题取最优 ⇒ 原问题取最优"就严格成立.
进一步:
- 分治: 不要求定序, 只要组合函数一致;
- 贪心: 多了 "无后效" + "贪心选择性质" 的假定;
- DP: 多了 "子问题集合有限、可枚举" 的假定.
记忆口诀: 假设越紧, 适用面越窄, 但换来的复杂度上界也越漂亮.
同一道题三种范式的不同表现
例子: 最长递增子序列 (Longest Increasing Subsequence, LIS).
分治解: 不适用
LIS 几乎不可分治: 左右两半的最优解无法在不重新扫描的情况下合并. 硬写成"分治 + 合并阶段交叉处理", 复杂度反而升到 O(n log² n) 或更高.
DP 解: 经典 O(n²)
dp[i] = max(dp[j] + 1), for j < i 且 a[j] < a[i]
dp[i] 依赖所有 dp[j] (j < i), 子问题重叠明显, 直接开表.
贪心 + 二分: O(n log n)
观察: 不需要保留整张 dp 表. 只需维护 tails[k] = 所有长度为 k+1 的递增子序列中末尾元素的最小值. 新元素比 tails 末端大则追加, 否则二分找到第一个大于等于它的位置替换掉.
这是一个 "DP + 结构性质 + 贪心化简" 的典型形式: DP 的完整表达不是必需的, 可以利用多余信息剪枝, 退化成贪心.
tip
"先写朴素 DP, 再找冗余状态退化成贪心/二分" 是刷题与工程通用的升级路径; LIS 的 tails 数组之所以能二分, 是因为它本身单调——发现这类单调性往往就是从 O(n²) 到 O(n log n) 的全部距离. 相关技巧见 搜索: 二分与三分.
warning
贪心的正确性必须证明 (交换论证 / 归纳 / 拟阵), 不能靠直觉. 反例俯拾皆是: 零钱面额 [1, 3, 4] 凑 6, 贪心给出 4+1+1 三枚, 最优却是 3+3 两枚. 见 贪心的交换论证与适用判据.
工程师视角: 怎么选范式
1. 子问题是否互不重叠、能直接合并?
是 → 分治.
2. 是否有"局部最优即全局最优"的证明 (或拟阵结构)?
有 → 贪心.
3. 子问题大量重叠?
是 → DP.
4. 已写出 DP, 但某一维可以被代数压缩?
是 → 剪掉那一维: 斜率优化 / 决策单调性 / 位运算压缩,
往往顺势退化成"DP + 二分"甚至纯贪心.
多语言同构
DP 在各语言里写法大同小异. 但工程上记忆化 vs 显式表给语言选用带来差异:
| 语言 | 记忆化写法 | 显式表写法 |
|---|---|---|
| Python | @lru_cache 一行 | dp[k] 显式迭代 |
| TS | 闭包 + memo Map | dp[]: number[] 迭代 |
| Go | map[state]int | 一维/二维循环 dp |
| C++ | vector<int> memo + 递归 | dp[...] 一维数组滚动 |
Python 的装饰器是最优雅的入口, 但大输入下 Python 递归有默认 ~1000 层深度限制且函数调用极慢, 最终仍要改成"拓扑序迭代". 工程上惯用的起步模式:
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i: int, j: int) -> int: ...
solve(0, n - 1)
但上规模后必须改写成 dp[i][j] 循环迭代——Python 递归太慢、太深、栈可能爆.
工程现实
DP 类问题在大规模业务工程里出现频率不高, 真实使用场景集中在:
- 序列对齐 (生物信息学);
- Viterbi 译码 (通信、语音);
- 强化学习的 value iteration / Q iteration;
- 矩阵链乘式的循环次序优化 (BLAS 内核调度);
- 路径规划: DP 配合 A* 或 Dijkstra 做启发剪枝.
DP 不会作为日常产品代码反复出现, 但在系统的某些"模型核心"位置反复出现: 你写的机器人控制、序列对齐、隐马尔可夫模型, 底层都先落到 DP.
这一章带走的东西
- 分治 / 贪心 / DP 是"分解约束"严格递增的同一族范式;
- 同一道题不一定三种范式都能解, 但各范式之间存在明确的退化路径;
- DP 是最适合充当"模型核心"的子问题显式表达框架;
- 各语言给出的语法表达差异很大, 但抽象完全同构;
- LIS 的尾部二分 = "DP 解出来之后用结构性单调剪枝退化成贪心"的经典模式.
一页速查
| 维度 | 分治 | 贪心 | DP |
|---|---|---|---|
| 子问题关系 | 独立不重叠 | 每步剪枝不回头 | 大量重叠 |
| 核心前提 | 组合函数一致 | 无后效 + 贪心选择性质 | 最优子结构 + 可枚举 |
| 正确性来源 | 归纳 | 交换论证 / 拟阵 (必须证明) | 最优子结构归纳 |
| 典型复杂度 | O(n log n) 主导项 | 通常最低 | 状态数 × 转移数 |
| 失败信号 | 合并代价爆炸 | 找不到反例却 WA | 状态空间爆炸 |
| 代表问题 | 归并排序 / FFT / 最近点对 | Kruskal / Huffman / 区间调度 | LCS / 背包 / 编辑距离 |