动态规划 · 数据结构与算法
怎么避免一遍又一遍地解同一个小问题？
课程目录为什么需要它
有些递归解法会把同样的调用重复几百万次。动态规划（DP）把每个小问题的答案只算一次并保存起来重复使用，把指数时间变成线性时间。路线规划、拼写检查，以及很多较难的面试题背后都是它。
直觉理解
爬楼梯，每次走 1 级或 2 级：到达第 n 级的方法数 = ways(n − 1) + ways(n − 2)。直接递归会一遍遍重复计算 ways(3)；每多一级，调用次数差不多翻一倍。
两种解决办法：
- 记忆化（自顶向下）：保留递归，但把答案存进字典。Python 的
@functools.lru_cache能帮你做。 - 填表（自底向上）：从最小的情况开始填一个列表：
ways[i] = ways[i-1] + ways[i-2]。
最难的是第一步：定义一个小答案是什么意思（「ways[i] = 到达第 i 级的方法数」），以及它怎么由更小的答案构成。
定义
动态规划
Solving a problem by combining answers to overlapping subproblems, computing each subproblem once.通过组合重叠子问题的答案来解决问题，每个子问题只算一次。
记忆化
Caching a function's results by its arguments, so repeated calls return instantly.按参数缓存函数的结果，重复调用时立即返回。
示例
数一数重复的工作
动手试试直接递归和记忆化递归，各调用了多少次。
calls = 0
def ways(n):
global calls
calls += 1
if n <= 1:
return 1
return ways(n - 1) + ways(n - 2)
print(ways(20), calls)
memo = {}
calls = 0
def ways_memo(n):
global calls
calls += 1
if n <= 1:
return 1
if n not in memo:
memo[n] = ways_memo(n - 1) + ways_memo(n - 2)
return memo[n]
print(ways_memo(20), calls)逐步执行
- L8每次调用又产生两次调用：次数爆炸。
- L1010946 种方法，21891 次调用。
10946 21891 - L20每个 n 只算一次。
- L24答案一样，只调用了 39 次。
10946 39
最少硬币，自底向上
动手试试best[a] 是凑出金额 a 所需的最少硬币数。从 0 开始往上填。
def fewest_coins(coins, amount):
INF = amount + 1
best = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and best[a - c] + 1 < best[a]:
best[a] = best[a - c] + 1
return best[amount] if best[amount] != INF else -1
print(fewest_coins([1, 3, 4], 6))
print(fewest_coins([5, 10], 3))逐步执行
- L30 个硬币凑出 0。INF 表示「目前还凑不出」。
- L6在凑出 a − c 的最佳方案上再加一枚 c。
- L103 + 3：两枚。（贪心的 4 + 1 + 1 要三枚。）
2 - L115 和 10 怎么组合都凑不出 3。
-1
常见错误
用贪心代替 DP
总是拿最大的硬币，在硬币 [1, 3, 4]、金额 6 时就会出错。当一个选择会影响后面的选择时，考虑 DP。
状态定义含糊
如果你没法用一句话说清 best[i] 是什么意思，递推式就会写错。先写下这句话。
小测验
1. 这段代码会输出什么？
ways = [1, 1]
for i in range(2, 6):
ways.append(ways[i - 1] + ways[i - 2])
print(ways)查看答案
答案：A
每一项都是前两项之和。
2. 什么样的问题适合用动态规划？
查看答案
答案：A
重叠子问题加上最优子结构：这时缓存才划算。
动手练习
3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。
- 预测输出填表
准确写出这段程序的输出。
- 改需求加上记忆化
grid_paths(r, c)计算在 r × c 的网格里，从左上角只向右或向下走到右下角的路径数。它是对的，但是指数级的。加上记忆化字典（或functools.lru_cache），让速度测试通过。 - 从零写最少硬币
写函数
fewest_coins(coins, amount)，返回凑出amount所需的最少硬币数；凑不出返回 -1。从 0 到 amount 建一张表best。
本课术语
| 术语 | 中文 | 英文定义 |
|---|---|---|
| Dynamic programming | 动态规划 | Reusing answers to overlapping subproblems instead of recomputing them. |
| Memoisation | 记忆化 | Caching a function's results by its arguments. |