动态规划
02-高级算法2026/11/14
动态规划把指数级的重复枚举压成多项式，核心不是背方程，而是先定义出一个可递推的状态。
做优惠券最优组合时，暴力枚举所有搭配在十几张券就会超时，而按面额拆成子问题后一次遍历就能出结果。文本折行、阶梯计价、路径计数也是同一类结构：当前决策只依赖少数几个更小的子问题。
三条边界
DP 与普通递归的差别是重叠子问题。斐波那契的朴素递归会把 f(3) 算很多遍，复杂度 O(2ⁿ)；把结果存下来后每个状态只算一次，降到 O(n)。
DP 与贪心的差别是无后效性要求。贪心每步取局部最优且不回头，零钱兑换里"尽量用大面额"在 [1,3,4] 凑 6 时会得到 4+1+1，而最优是 3+3；DP 保留所有子问题的最优值，所以能得到正确答案。无后效性指当前状态一旦确定，后续决策不再受之前路径影响，这是能写出转移方程的前提。
五步法
- 用一句话定义
dp[i]或dp[i][j]的含义，必须包含"前 i 个""以 i 结尾"这类限定。 - 写出状态转移，即当前状态由哪些更小的状态推导而来。
- 确定初始化，也就是递推的起点和边界。
- 确定遍历顺序，保证用到的状态已经算好。
- 用小数据手推一遍，验证输出与预期一致。
从递归到递推
以斐波那契为例，三种写法是同一个状态方程的三种求值顺序。
// 1. 暴力递归：时间 O(2ⁿ)，空间 O(n)
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
// 2. 记忆化搜索：时间 O(n)，空间 O(n)
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const res = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, res);
return res;
}
// 3. 递推 + 滚动变量：时间 O(n)，空间 O(1)
function fibDP(n) {
if (n <= 1) return n;
let prev = 0, cur = 1;
for (let i = 2; i <= n; i++) [prev, cur] = [cur, prev + cur];
return cur;
}
记忆化保留了递归的思考方式，只是加了缓存；递推则要求先想清楚依赖方向。做题时先用记忆化把答案写对，再改写成递推，是最稳的路径。
滚动数组与遍历方向
二维背包 dp[i][j] 表示前 i 个物品、容量 j 的最优值，它只依赖上一行，所以可以压成一维。压维之后，遍历方向决定了 dp[j - w] 读到的是上一行还是本行。
// 01 背包：每件物品最多一次，容量必须倒序
function knapsack01(weights, values, capacity) {
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let j = capacity; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
// 完全背包：每件物品无限次，容量正序
function knapsackComplete(weights, values, capacity) {
const dp = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let j = weights[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
倒序时 dp[j - w] 还没被本轮更新，等价于上一行的值，物品只会被选一次；正序时它已被本轮更新，等价于同一行，物品可以再选一次。这就是"01 背包倒序、完全背包正序"的全部原因。
题型分类
| 类型 | 状态定义 | 代表题 |
|---|---|---|
| 线性 DP | 前 i 个元素的最优值 | 爬楼梯、打家劫舍、最大子数组和 |
| 序列 DP | 以 i 结尾的最优值 | 最长递增子序列、最长公共子序列、编辑距离 |
| 区间 DP |