动态规划：从重叠子问题到记忆化
2.2 动态规划：从重叠子问题到记忆化
本节摘要：动态规划是全册进化链上最陡的一段跃迁。本节沿着爬楼梯到零钱兑换的路线，讲清"重叠子问题加最优子结构"两个成立条件，演示自顶向下记忆化与自底向上递推两条等价路线，完整走一遍状态定义、转移方程、初始化、遍历顺序的设计流程，最后用滚动数组完成空间压缩。
从递归树上长出来的方法
上一节的斐波那契递归树留了个尾巴：重复节点只算一次，就把指数压成线性。动态规划就是这句话的体系化。但不是所有问题都能享受这份红利，成立条件有两个。重叠子问题：递归展开后，相同的子问题大量反复出现——斐波那契的 3 被反复计算，重叠成立；二分查找每次砍掉一半，子问题互不相同，无从重叠。最优子结构：原问题的最优解可以由子问题的最优解构造出来——爬到第 n 阶的最优走法由第 n 减一阶或第 n 减二阶的最优走法一步推出。两个条件缺一个，硬套 DP 只会写出正确而缓慢的代码。
一、入门题：爬楼梯的完整推演
题目：你在爬 n 阶楼梯，每次能上一阶或两阶，问有多少种走法。先写暴力递归——走法数 f(n) 等于 f(n 减一) 加 f(n 减二)（最后一步要么从 n 减一阶跨一阶上来，要么从 n 减二阶跨两阶上来），基准 f(0) 等于 f(1) 等于 1。这和斐波那契同构，指数级。按上节经验加备忘录，线性化；再进一步发现每个状态只依赖前面两个状态，递归都可以省掉，直接迭代：
def climb_stairs(n): if n <= 2: return n a, b = 1, 2 # f 的第 1 项与第 2 项 for _ in range(3, n + 1): a, b = b, a + b # 滚动前进 return b print(climb_stairs(3)) # 输出 3（1 加 1 加 1、1 加 2、2 加 1） print(climb_stairs(10)) # 输出 89
注意空间演进的三级台阶：备忘录版 O(n) 空间存全部状态；数组递推版 O(n)；滚动变量版 O(1)。三级台阶对应"记忆化、递推、压缩"三个阶段，绝大多数线性 DP 都能走完这三级。面试时主动演示这个演进过程，比直接报出最终答案的含金量高得多。
二、设计流程四步法：以零钱兑换为例
爬楼梯太简单，看不出设计难度。换零钱兑换：面额数组 coins 与总额 amount，求凑出总额的最少硬币数，每种面额无限用。按四步走。第一步定义状态：dp[i] 表示凑出金额 i 的最少硬币数——状态定义是 DP 的灵魂，定义错了后面全错。第二步转移方程：dp[i] 等于对所有面额 c 的 min(dp[i 减 c] 加一)——凑 i 的最后枚硬币一定是某种 c，倒推回去就是子问题。第三步初始化：dp[0] 等于 0（凑零元零枚硬币），其余设为无穷大表示"暂时凑不出"。第四步遍历顺序：自底向上从小金额到大金额，保证算 dp[i] 时所有 dp[i 减 c] 已就绪。
def coin_change(coins, amount): INF = amount + 1 # 相当于无穷大，且不可能被更新超过 dp = [0] + [INF] * amount for i in range(1, amount + 1): for c in coins: if c <= i and dp[i - c] + 1 < dp[i]: dp[i] = dp[i - c] + 1 return dp[amount] if dp[amount] <= amount else -1 print(coin_change([1, 2, 5], 11)) # 输出 3（5 加 5 加 1） print(coin_change([2], 3)) # 输出 -1（凑不出）
时间 O(amount 乘面额种数)，空间 O(amount)。对照暴力：枚举所有硬币组合是指数级的，DP 把它压成多项式，压掉的正是组合枚举中天文数字的重复子问题。同一题的变式问"凑法总数"而非"最少枚数"，只需把 min 换成累加：dp[i] 累加 dp[i 减 c]，但要注意遍历顺序——外层金额内层硬币求的是组合数，外层硬币内层金额求的是排列数，这个顺序之差是高频考点。
递归树去重前后对比
三、两条路线与一个压缩技巧
自顶向下（记忆化递归）与自底向上（数组递推）是等价的两条路线，选择标准很实际：状态转移图复杂、有些状态可能永远用不到时，递归按需计算更省；状态天然线性或二维有序时，递推更直观且没有栈溢出风险。面试中先说清用哪条路线以及为什么，是标准的加分动作。空间压缩的通用判据：dp[i] 只依赖固定窗口内的历史状态时，窗口外的都可以丢。二维的情况更常见——编辑距离、背包问题的 dp[i][j] 只依赖上一行，二维表就能压成一行滚动数组，空间从 n 乘 m 降到 m。压缩是"优化"而非"必须"，建议先写不压缩的版本确保正确，再压缩。
四、易错诊断：DP 写错时的排查顺序
动态规划的出错模式相当固定，按序排查能覆盖绝大多数情况。第一步查状态定义：把 dp 数组含义写成一句自然语言，检查代码里每处读写是否与这句话一致——状态定义含糊（"dp[i] 表示前 i 个的最优"，到底是含第 i 个还是不含）是最常见的事故源，零钱兑换里"凑出金额 i"很清晰，但打家劫舍类题"考虑前 i 间且不相邻"就两种写法都成立，选定一种后全篇贯彻。第二步查转移的完备性：转移方程是否覆盖了所有取得最优的方式，爬楼梯只有两种来路，打家劫舍有"偷与不偷"两种决策，漏一种就系统性偏差。第三步查初始化与边界：dp[0] 是不是语义正确的基准（凑零元的零枚硬币），无穷大的替代值是否大到不可能被超越又小到不引起溢出。第四步查遍历顺序：算 dp[i] 时依赖项是否都已就绪，压缩空间时方向是否正确。
拿打家劫舍做个快诊示范：一条街上相邻房屋不能同偷，求最大金额。状态定义为 dp[i] 表示考虑前 i 间能偷到的最大金额，转移为 dp[i] 等于 max(dp[i 减一]（不偷第 i 间）, dp[i 减二] 加当前值（偷第 i 间）)，初始化 dp[0] 等于零、dp[1] 等于第一间的金额。依赖窗口宽度为二，滚动两变量压缩，空间 O(1)。
def rob(nums): prev, cur = 0, 0 for x in nums: prev, cur = cur, max(cur, prev + x) return cur print(rob([1, 2, 3, 1])) # 输出 4（偷第 1 与第 3 间） print(rob([2, 7, 9, 3, 1])) # 输出 12（偷 2、9、1）
空数组用例下这段代码恰好返回零，属于"碰巧对"——若题目要求空输入报错就得加前置判断。碰巧对与必然对的区别，正是面试官爱深挖的地方：能说清"为什么空输入返回零在语义上成立"（考虑零间房屋可偷金额为零），才说明状态定义真的吃透了。
本节要点回顾
- 两个成立条件：重叠子问题让记忆有意义，最优子结构让转移成立，缺一不可；
- 状态定义是灵魂：dp 数组的含义要用一句自然语言说清，说不清就是没想清；
- 四步设计流程：定义状态、写转移、初始化、定遍历顺序，按序执行不易漏；
- 组合与排列之分：求组合数外层遍历物品，求排列数外层遍历金额；
- 压缩是最后一步：先写正确的不压缩版，确认只依赖固定窗口后再压。
下一节处理另一类问题：不问最优值、而问所有方案。解空间从表格变成一棵树，进化的关键词也从"记忆"换成"剪枝"。