入门：最优子结构、重叠子问题与三要素
基于通用算法概念 · 核于 2026-07
速查
- DP 是什么：一套「把大问题拆成语义相同的小问题、合并小问题解得到大问题解」的方法论——不是具体算法，是思想框架，核心抓住两个特征：最优子结构 + 重叠子问题。
- 最优子结构：大问题的最优解由子问题的最优解构成（如「爬到第 n 阶的方案数 = 爬到第 n-1 阶 + 爬到第 n-2 阶」）——是 DP / 分治能用的前提。
- 重叠子问题：不同的递归分支会反复求解同一个子问题（如
fib(5)会算fib(3)两次、fib(2)三次）——是 DP 区别于分治的关键：分治的子问题不重叠（归并排序），DP 的子问题重叠，所以记下来避免重复算。 - 三要素：①状态定义（
dp[i]代表什么）；②状态转移方程（dp[i]怎么由更小的子问题推出）；③边界条件（最小的、不依赖转移的那几个dp值）。 - 两种实现：自顶向下 = 记忆化递归（从大问题出发递归 + 用数组/哈希记已算结果，更贴近思考过程）；自底向上 = 递推填表（从边界往大算，迭代填
dp数组，常数更小、无递归栈）。两者等价，复杂度相同。 - 与分治的区别：分治的子问题独立不重叠（归并排序左右两半各算各的），不需要记忆化；DP 的子问题重叠，必须记下来才省时间——这是本质分水岭。
- 与贪心的区别：贪心每步选「当前最优」不回头，需严格证明局部最优能推出全局最优；DP 枚举所有子问题选择取最优，适用面更广但常数更大。能用贪心优先贪心（更快），不行再 DP。
- 斐波那契是 DP 的 Hello World：
fib(n) = fib(n-1) + fib(n-2)，暴力递归 O(2ⁿ)，记忆化 / 递推后 O(n)——完美演示「重叠子问题 + 记忆化」的威力。 - DP 不是万能：要求「无后效性」（当前状态之后的过程不会影响之前的状态），不满足（如带「历史路径」约束）就要扩展状态维度。
- 进阶顺序：背包问题与零钱兑换 → DP 设计方法与常见模型 → 参考。
一、核心思想：从暴力递归到 DP
理解 DP 最好的入口是斐波那契数列：fib(1)=1, fib(2)=1, fib(n)=fib(n-1)+fib(n-2)。最朴素的写法是直接翻译递推式：
function fib(n) {
if (n <= 2) return 1; // 边界
return fib(n - 1) + fib(n - 2); // 递归
}这个写法正确但慢得离谱：fib(5) 会算 fib(4)+fib(3)，fib(4) 又算 fib(3)+fib(2)——fib(3) 被算了两次，越往下重叠越多。整体复杂度是 O(2ⁿ)，fib(50) 就算到天荒地老。
为什么慢？因为同一个子问题被反复求解。这就是 DP 抓住的第一个特征：重叠子问题。
记忆化：记下来别重复算
既然子问题会重叠，那就把算过的结果存起来，下次直接查：
const memo = new Map(); // 记忆化表
function fib(n) {
if (n <= 2) return 1;
if (memo.has(n)) return memo.get(n); // 算过就直接拿
const r = fib(n - 1) + fib(n - 2);
memo.set(n, r); // 记下来
return r;
}每个 fib(i) 只真正计算一次，共 n 个子问题，每个 O(1)——复杂度从 O(2ⁿ) 降到 O(n)。这就是「自顶向下记忆化」。
递推：从边界往大算
换个角度，直接从已知边界（fib(1)=1, fib(2)=1）往大填表：
function fib(n) {
const dp = new Array(n + 1);
dp[1] = 1; dp[2] = 1; // 边界
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 转移
}
return dp[n];
}这就是「自底向上递推」——不需要递归栈，常数更小，还能滚动数组优化到 O(1) 空间。记忆化和递推是同一件事的两种写法，复杂度相同，选哪个看习惯和题目。
二、两个核心特征
DP 能用，必须同时满足两个特征：
- 最优子结构：大问题的（最优）解可以由子问题的（最优）解组合而成。爬楼梯：到第 n 阶的方案 = 到第 n-1 阶的方案 + 到第 n-2 阶的方案。背包：容量 w 下前 i 件物品的最大价值 = max（不装第 i 件，装第 i 件）。没有这个性质，DP 无从下手。
- 重叠子问题：不同的求解路径会反复遇到同一个子问题。斐波那契的
fib(3)被多次调用；背包的「前 i 件、容量 w」会被不同物品组合反复查询。有了重叠，记忆化 / 递推才有意义——分治的子问题不重叠，记下来也没用。
一句话区分：有最优子结构 → 可以用 DP / 分治；再加上重叠子问题 → 用 DP（记忆化）才有收益。
三、三要素：状态、转移、边界
任何 DP 题都可以拆成三件事：
- 状态定义：
dp[...]代表什么。这是最难也最关键的一步——状态定义错了，转移方程再漂亮也白搭。如斐波那契dp[i]= 第 i 个斐波那契数；爬楼梯dp[i]= 爬到第 i 阶的方案数。 - 状态转移方程：
dp[i]怎么由更小的子问题推出。这是 DP 的「灵魂」。fib(i) = fib(i-1) + fib(i-2)、dp[i] = dp[i-1] + dp[i-2]。 - 边界条件：最小的、不依赖转移的那几个初始值。
fib(1)=1, fib(2)=1、dp[1]=1, dp[2]=2。漏边界或边界写错是 DP 最常见的 bug。
记住解题流程：先想暴力递归 → 观察重叠子问题 → 加记忆化 → （可选）改递推 → （可选）空间优化。
四、记忆化 vs 递推：怎么选
| 维度 | 自顶向下（记忆化递归） | 自底向上（递推填表） |
|---|---|---|
| 思考方向 | 从大问题出发，递归到边界 | 从边界出发，迭代填到大 |
| 代码形态 | 递归函数 + memo | for 循环 + dp 数组 |
| 贴近直觉 | ✅ 更贴近「人脑推导转移」 | 需先想清计算顺序 |
| 子问题覆盖 | 只算「真正用到」的子问题 | 把所有子问题都算一遍（可能有些用不到） |
| 常数 / 栈 | 有递归栈开销，可能栈溢出 | 无栈，常数更小 |
| 空间优化 | 难滚动优化 | ✅ 易做滚动数组 / 一维化 |
经验法则：新手先用记忆化把思路理顺（更不容易写错转移），再改递推拿常数优势；状态空间稀疏（很多子问题用不到）时用记忆化省时间；要空间优化时用递推。
五、与分治、贪心的区别
| 范式 | 子问题关系 | 是否记忆化 | 典型 |
|---|---|---|---|
| 分治 | 独立、不重叠 | 不需要 | 归并排序、快排 |
| DP | 重叠 | 必须记 | 斐波那契、背包、LCS |
| 贪心 | 不显式划分子问题，每步选当前最优 | 不需要 | 活动选择、Dijkstra |
- DP vs 分治：都「分而治之」，分水岭是子问题是否重叠。归并排序分两半，两半各算各的、互不重叠，所以 O(n log n) 就够，不需要记忆化；斐波那契两半严重重叠，不记就 O(2ⁿ)。
- DP vs 贪心：贪心不回头，每步选局部最优，需严格证明「局部最优 ⇒ 全局最优」（如区间调度按结束时间排序）。DP 穷举所有子选择取最优，适用面更广但常数更大。能用贪心优先贪心（更快、代码更短），证不出贪心正确性就用 DP 兜底。
六、一个隐藏前提：无后效性
DP 还有个常被忽略的前提：无后效性——「当前状态之后的过程不会影响之前的状态」，即未来不依赖「怎么到达当前状态」的路径，只依赖当前状态本身。
- 爬楼梯满足：
dp[i]只看dp[i-1]、dp[i-2]，不关心你是 1 步还是 2 步爬到i-1的。 - 反例：「从左上到右下，要求路径上恰好经过 k 个障碍」——光知道当前坐标不够，还得记「已经经过几个障碍」，状态要加一维
dp[i][j][k]。这就是「状态定义要包含所有影响未来的信息」。
不满足无后效性时，扩展状态维度把「历史信息」吸收进状态里，往往就能继续用 DP。
下一步
理解了 DP 的核心思想与三要素后，下一步是 DP 最经典的「Hello World」家族——背包问题与零钱兑换，它们把「选或不选」的状态转移演绎到极致，并演示二维压一维的空间优化技巧，见背包问题与零钱兑换。