课程 · #11 / 11

动态规划

以空间换时间——解一次，永远记住

Dynamic programming · 1D table fill

…

speed step 0 / 0

试一试： 看着一维表格从左到右填充——每个单元格就是前两个单元格之和。朴素递归会重复计算数十亿次的值，只需从相邻单元格读取一次。这个转变——重新计算 → 查表——就是动态规划的全部精髓。

为什么它重要

数量惊人的"指数级"问题其实暗地里是多项式级的——它们只是看起来像指数级，因为那个显而易见的递归把同一个子问题求解了上百万次。动态规划正是这样一种技巧：察觉到这种重复，并把它缓存下来。一旦你看穿了这个套路，那些原本要算上几个世纪的问题，会坍缩到几毫秒。

在机器人领域，它是值迭代、策略迭代、贝尔曼递归，以及你已经见过的最短路径算法的根基。在字符串领域，它是 git 使用的 diff 算法。在生物信息学领域，每一个序列比对工具都靠它运作。

核心思想

一个具备 DP 形状的问题有两条性质：

最优子结构——整个问题的最优解，可以由同一问题的更小版本的最优解搭建起来。
重叠子问题——那些更小的版本会重复出现。朴素递归会把同一个子问题求解很多次。

当两者都成立时，诀窍就是把每个子问题恰好求解一次并把结果存起来。有两种风味：

记忆化（自顶向下）： 保留递归；缓存每次调用的返回值。第一次碰到 f(7) 时你计算它；此后就直接读缓存。
制表（自底向上）： 彻底丢掉递归。从最小的子问题一路填到完整的那一个，填满一个数组（或二维表）。每个格子的值都是你已经填好的那些格子的函数。

两者都是 O(状态数 × 每个状态的工作量)。记忆化更贴近天然的递推关系；制表则让你对空间和填表顺序有更精细的掌控。

要点回顾

DP = 递归 + 一个确保每个子问题只被求解一次的缓存。
最难的部分是找到状态——f(i, j, k…) 需要知道什么才能给出它的答案？
一旦递推关系正确，时间复杂度就是 (状态数) × (每个状态的工作量)。
一维问题常常能从 O(n) 空间坍缩到 O(1)，只需保留最后几个格子（滚动）。
二维问题常常能从 O(m·n) 坍缩到 O(min(m, n))，只需每次只保留一行。

再深入一些

识别 DP 形状

对任何你怀疑是 DP 的问题，问自己五个问题：

我能不能递归地描述这个答案？ "到达状态 X 的最小代价，等于在所有选择 Y 上取最小的……"
状态是什么？ 一个整数？一个二元组 (i, j)？一个下标加一个标志位？
递推关系是什么？ f(state) 如何分解为 f(更小的状态)？
基本情形是什么？ 那些无需递归就已知答案的最小状态。
我该以什么顺序填表？ 任何能保证每个格子的依赖项都在它之前被填好的顺序。

如果这五个你都能回答，你就能写出这个 DP。如果不能，那你还没拿到一个 DP 问题——回去重新陈述它。

记忆化与制表 —— 何时选哪个

| | 记忆化 | 制表 | |---|---|---| | 思维模型 | 自顶向下：信任递归 | 自底向上：逐块搭建 | | 实现方式 | 递归函数 + 缓存 | 循环填充数组 | | 求解的子问题 | 只求那些可达的 | 全部都求 | | 栈的风险 | 深递归 → 栈溢出 | 无 | | 空间优化的潜力 | 较难 | 容易（滚动行 / "最后两个值"） |

当状态空间稀疏时——状态有很多，但答案只依赖于一小撮可达的状态——选记忆化。当你反正会触及大部分状态空间、或当你需要做空间优化时，选制表。

空间优化 —— "滚动"技巧

大多数 DP 递推只依赖于紧邻的前一行，或常数个之前的格子。所以你并不需要完整的表。

斐波那契只需要 f(n-1) 和 f(n-2) → O(1) 空间。
m × n 上的 LCS 只依赖于前一行 → O(min(m, n)) 空间。
背包只需要前一个容量列 → O(W) 空间。

盯住递推关系：如果 f(i) 对小的 k 只用到 f(i-1), f(i-2), …, f(i-k)，你就可以只保留那 k 个值并滑动前进。

机器人锚点 —— DP 即贝尔曼即值迭代

强化学习中的贝尔曼方程，字面上就是一个 DP 递推：

V*(s) = max over actions a of [ R(s, a) + γ · Σ P(s' | s, a) · V*(s') ]

状态 s 的最优价值，等于即时奖励加上最佳下一状态的折扣未来价值。值迭代不过就是在状态空间上对贝尔曼递推的制表，迭代到收敛为止。每一个网格世界求解器、每一个处理代价的路径规划器、教科书里每一个 MPC 控制器——它们都是 DP。

DP 何时会失效

DP 需要最优子结构。有些问题违反它：

一般图中的最长简单路径（没有 DP——NP 难）。
任何未来选择依赖于完整历史、而不只是某个可汇总状态的问题。

如果你找不到一个能囊括未来步骤所需全部信息的有限状态，那 DP 就用不上。

实战中的 DP

diff 算法（git diff、diff -u）用 O(m·n) 计算最长公共子序列——正是下面的第三道题。
不确定性下的机器人规划用值迭代/策略迭代——两者都是状态空间上纯粹的 DP。
计算生物学中的序列比对（Needleman-Wunsch、Smith-Waterman）是在一张二维编辑表上的 DP。
语音识别的维特比算法寻找最可能的隐状态序列——在网格图上的 DP。
编译器的寄存器分配在表达式树上用 DP。
路由协议（OSPF、BGP 路径选择）——Bellman-Ford 就是在图距离上的 DP。

数学细节

时间: O(状态数 × 每个状态的工作量)——一旦你选定了状态表示，这就是精确值。
空间（完整表）: O(状态数)
空间（滚动）: 常常是 O(d)，其中 d 是递推的"回看深度"——通常是一个小常数或一行。
记忆化的额外开销: HashMap 查找 + 递归栈——相比一个紧凑的制表循环有 2-3 倍的常数因子。对稀疏状态空间来说这是值得的。

实现

骨架 —— 每个 DP 都套得进这个模板

def solve():
    memo = {}
    def f(state):
        if state in BASE_CASES: return base_answer
        if state in memo: return memo[state]
        result = combine(f(smaller_state_1), f(smaller_state_2), ...)
        memo[state] = result
        return result
    return f(initial_state)

或者，制表版：

def solve():
    dp = [base_answer for _ in range(N + 1)]
    for state in range(SMALLEST + 1, LARGEST + 1):
        dp[state] = combine(dp[smaller_1], dp[smaller_2], ...)
    return dp[LARGEST]

经典问题形状

一维线性：f(n) = combine(f(n-1), f(n-2))——斐波那契、爬楼梯、打家劫舍
一维无界：f(amount) = min over coins of f(amount - coin) + 1——零钱兑换、切钢条
二维：f(i, j) = combine(f(i-1, j), f(i, j-1), f(i-1, j-1))——LCS、编辑距离、网格路径
区间：f(i, j) = min over splits k of f(i, k) + f(k, j) + cost(i, j, k)——矩阵链乘、最优 BST
树形 DP：后序遍历，每个节点的答案由其孩子的答案组合而成——直径、最大路径和

练习

三道题目，把三种最基础的 DP 形状牢牢锁定：

爬楼梯 —— 简单 · 一维斐波那契形状；记忆化 → 制表 → O(1) 空间的演进
零钱兑换 —— 中等 · 一维无界背包；"在选择上取最小"的递推
最长公共子序列 —— 中等 · 二维表；每一个 diff 工具的基础

→ 浏览全部练习题

🧮 动态规划