第 100 章 DP 入门¶
本章配套 9 道例题，见 §例题。
动态规划是笔试里出现频率最高的算法族。这一章不讲任何具体模型，只讲怎么把一个问题 变成 DP——这套方法论用得熟，后面四章的模型都只是它的实例。
1 从贪心的失败讲起¶
先看一个经典的开场例子。
硬币问题：有面值 \(1, 5, 11\) 的硬币各无限枚，凑出 \(15\) 最少要几枚？
贪心的想法是「每次拿最大的」：\(11 + 1 + 1 + 1 + 1 = 15\)，用了 5 枚。
但正确答案是 \(5 + 5 + 5 = 15\)，只要 3 枚。
贪心为什么错？因为它鼠目寸光——拿了 \(11\) 之后，剩下的 \(4\) 只能用 \(1\) 来凑， 这个代价在做决策时看不见。而如果面值是 \(1, 5, 10\)（人民币），贪心恰好是对的。 贪心的正确性依赖于面值的特殊结构，不是普适的。
DP 的做法是：不去猜哪个决策好，而是把每种决策都试一遍，并复用子问题的答案。
# [片段]
INF = float("inf")
f = [0] + [INF] * n # f[0] = 0：凑 0 元不需要硬币；其余先设成「凑不出」
for x in range(1, n + 1): # 从小到大算，保证用到 f[x-c] 时它已经算好了
for c in (1, 5, 11): # 枚举「最后一枚硬币」是哪种面值
if x >= c and f[x - c] + 1 < f[x]: # 面值不能超过剩余金额
f[x] = f[x - c] + 1 # 拿掉这一枚，剩下的正是子问题 f[x-c]
DP 与贪心的本质区别：贪心在每一步扔掉其余选项，DP 把所有选项都算完再取最优。 DP 比暴力搜索快，是因为它把重复的子问题只算一次。
2 DP 的两个前提¶
一个问题能用 DP，必须同时满足两条。
无后效性¶
当前状态一旦确定，未来的决策就与「怎么走到这个状态」无关。
数楼梯里，「现在站在第 \(i\) 阶」这个状态包含了未来所需的全部信息—— 从 \(i-1\) 迈上来还是从 \(i-2\) 跳上来，对后面的走法毫无影响。所以无后效性成立。
反例：如果题目说「不能连续两次迈 2 阶」，那么「站在第 \(i\) 阶」就不够了， 未来还依赖「上一步迈了几阶」。这时要把状态加宽：
这是设计 DP 状态的核心动作：发现无后效性不成立时，不是放弃 DP， 而是把缺失的信息补进状态里。BISHI135 就是反例——它看起来需要补一维， 实际上换个坐标系就不用了，见 线性DP。
最优子结构¶
大问题的最优解，由子问题的最优解拼成。
凑 \(15\) 的最优方案里，如果最后一枚是 \(5\)，那么凑 \(10\) 的那部分必然也是最优的—— 否则把它换成更优的方案，总方案会更优，矛盾。
反例：求「路径上数字之和为质数」的路径。子路径的和是质数，并不能推出总和是质数， 子问题的「最优」在这里没有意义。
3 设计一个 DP 的四步法¶
这是推荐的固定流程，四步缺一不可。
| 步骤 | 要回答的问题 | 数楼梯的答案 |
|---|---|---|
| 1. 状态 | 用什么变量刻画「一个局面」？ | \(f_i\) = 走到第 \(i\) 阶的方案数 |
| 2. 转移 | 这个局面能由哪些更小的局面得到？ | 最后一步从 \(i-1\) 迈 1 阶，或从 \(i-2\) 迈 2 阶 |
| 3. 边界 | 最小的局面是什么？ | \(f_1 = 1\)，\(f_2 = 2\) |
| 4. 目标 | 答案对应哪个状态？ | \(f_n\) |
转移的推导有一个万能技巧：枚举「最后一步」。
问「走到第 \(i\) 阶的方案数」，就问「最后一步是怎么走的」。最后一步只可能是迈 1 阶 或迈 2 阶，这两类方案互不重叠（最后一步的长度不同）且覆盖全部情况， 所以直接相加：
「互不重叠 + 覆盖全部」是计数类 DP 的正确性依据，必须显式检查这两条。 漏了会算少，重了会算多——重复计数是计数 DP 最常见的错误。
对最优化类 DP，把加法换成 \(\min\) / \(\max\) 即可，这就是 BISHI132 与 BISHI131 的关系。
4 两种实现：递推 vs 记忆化¶
同一个 DP 有两种写法。
递推（自底向上）¶
# [片段]
f = [0] * (n + 1)
f[1], f[2] = 1, 2 # 边界：1 阶只有 1 种走法，2 阶有「1+1」和「2」两种
for i in range(3, n + 1): # 正序：算 f[i] 时 f[i-1]、f[i-2] 都已经就位
f[i] = f[i - 1] + f[i - 2] # 按「最后一步迈 1 阶 / 迈 2 阶」分类，两类不重不漏
记忆化搜索（自顶向下）¶
# [片段]
from functools import lru_cache
@lru_cache(maxsize=None) # 缓存所有算过的 f(i)，同一个状态只真正展开一次
def f(i):
if i <= 2: # 边界恰好满足 f(1)=1、f(2)=2，可以合并成一句
return i
return f(i - 1) + f(i - 2) # 依赖关系由递归自动处理，不用操心枚举顺序
| 递推 | 记忆化 | |
|---|---|---|
| 代码量 | 稍多 | 少，几乎就是把公式抄一遍 |
| 需要想清楚 | 枚举顺序 | 不需要，递归自动处理依赖 |
| 只算用得到的状态 | ❌ 全算 | ✅ 按需 |
| Python 性能 | 快 | 慢 5–20 倍（函数调用 + 缓存查表） |
| 递归深度 | 无风险 | \(n = 10^5\) 直接 RecursionError |
在 Python 里，能写递推就不要写记忆化。 这不是风格问题：CPython 的函数调用开销极大，而记忆化搜索每个状态至少一次调用。 \(10^6\) 个状态的记忆化搜索通常要几秒，同样的递推只要 0.1 秒。
记忆化的价值在于状态空间稀疏（大部分状态用不到）或转移顺序难以确定（如博弈、图上 DP）。 详见 记忆化搜索与剪枝。
5 滚动数组¶
数楼梯的 \(f_i\) 只依赖 \(f_{i-1}\) 和 \(f_{i-2}\)，那就没必要存整个数组：
# [片段]
a, b = 1, 2 # a、b 始终是「相邻两阶」的答案，初值为 f[1], f[2]
for _ in range(3, n + 1): # 循环变量用不上，只关心迭代次数
a, b = b, (a + b) % MOD # 右边整体先算完再赋值，等价于同时更新两个变量
空间从 \(O(n)\) 降到 \(O(1)\)。滚动的三种形态：
| 依赖关系 | 滚动方式 |
|---|---|
| \(f_i\) 只依赖 \(f_{i-1}, f_{i-2}\) | 两个标量变量 |
| \(f[i][\cdot]\) 只依赖 \(f[i-1][\cdot]\) | 两个一维数组交替，或直接原地倒序更新 |
| \(f[i][j]\) 依赖 \(f[i-1][j], f[i][j-1]\) | 一维数组原地正序更新 |
背包的一维写法就是滚动数组，而「倒序还是正序」的区别正好对应 01 背包与完全背包。 这是全书最经典的一个细节，见 背包问题。
Python 里滚动数组还有一个额外好处：数组更短 ⇒ 更容易整段丢给 C 层批处理， 详见 §7。
6 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI131 | 数楼梯 | 简单 | 题解 |
| BISHI132 | 小红的地砖 | 简单 | 题解 |
| BM62 | 斐波那契数列 | 入门 | 题解 |
| BM63 | 跳台阶 | 简单 | 题解 |
| BM64 | 最小花费爬楼梯 | 简单 | 题解 |
| LC62 | 不同路径 | 中等 | 题解 |
| LC64 | 最小路径和 | 中等 | 题解 |
| LC70 | 爬楼梯 | 简单 | 题解 |
| LC118 | 杨辉三角 | 简单 | 题解 |
BISHI131 数楼梯（简单）¶
每步走 1 或 2 阶，求走到第 \(n\) 阶的方案数，对 \(998244353\) 取模。\(n \le 10^5\)。
四步法直接套用，就是上面的 \(f_i = f_{i-1} + f_{i-2}\)，也就是斐波那契数列（错开一位）。
import sys
MOD = 998244353
def main():
n = int(sys.stdin.buffer.read().split()[0])
if n == 1: # n=1 时下面的循环一次都不跑，b 会停在 f[2] 上
print(1)
return
a, b = 1, 2 # f[1] = 1, f[2] = 2
for _ in range(3, n + 1): # 每轮把窗口往前挪一阶，结束时 b 就是 f[n]
a, b = b, (a + b) % MOD # 每步取模，f 始终是十位以内的小整数
print(b % MOD) # n=2 时 b 还没取过模，这里补一次
main()
三个坑：
- \(n = 1\) 要特判，否则 \(f_2\) 的初值会被当成答案输出。
- 每步都要取模。Python 大整数不会溢出，但 \(f_{10^5}\) 有约 2 万位， 大整数加法退化成 \(O(\text{位数})\)，总复杂度变成 \(O(n^2/64)\)，白慢几十倍。 这是 Python 特有的陷阱——C++ 选手不取模是「答案错」，Python 选手不取模是「超时」。
- \(n \le 10^5\) 用不着矩阵快速幂。矩阵加速见 DP优化。
题解：solutions/nowcoder/BISHI131/sol.py（已通过官方样例验证）
BISHI132 小红的地砖（简单）¶
从第 1 块走到第 \(n\) 块，每步走 1 或 2 格，踩到第 \(i\) 块消耗体力 \(a_i\)，求最小总体力。
这题和 BISHI131 是同一个 DP，只是把「计数的加法」换成了「求最优的 min」。
含义：走到第 \(i\) 块必然是从 \(i-1\) 或 \(i-2\) 迈过来的，而无论从哪来，踩上 \(i\) 都要付 \(a_i\)。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
if n == 1: # 只有一块地砖时不用走，也就不消耗体力
print(0)
return
prev2, prev1 = a[0], a[0] + a[1] # f[1], f[2]：第 2 块只能由第 1 块迈过来
for i in range(2, n): # 下标 i 对应第 i+1 块地砖
# 从 i-1 或 i-2 迈过来都要踩上 a[i]，所以先取两者较小再加 a[i]
prev2, prev1 = prev1, a[i] + (prev1 if prev1 < prev2 else prev2)
print(prev1) # 循环结束时 prev1 就是 f[n]
main()
计数 DP 与最优化 DP 是同构的：状态、转移、边界的推导完全一样， 只是合并子问题时一个用 \(+\)、一个用 \(\min\)/\(\max\)。 把这两题放在一起看，能省下一半的学习成本。
题解：solutions/nowcoder/BISHI132/sol.py（已通过官方样例验证）
面试题单里的三道入门题¶
这三道题可以直接拿来练 §3 的四步法——动态规划的入门题几乎都长成这个样子。
斐波那契数列与 跳台阶是同一个递推的两种题面： \(f_i = f_{i-1} + f_{i-2}\)，差别只在边界。 跳台阶的 \(f_1 = 1, f_2 = 2\)，斐波那契的 \(f_1 = f_2 = 1\)—— 四步法里的「边界」这一步就是为这种差别准备的，状态与转移一模一样时， 写错的地方必然在边界上。两题都只依赖前两项，按 §5 滚成两个变量即可，空间 \(O(1)\)。
最小花费爬楼梯把计数换成了最优化：每级台阶有代价，求登顶的最小总代价。 转移从 \(f_{i-1} + f_{i-2}\) 变成 \(\min(f_{i-1} + c_{i-1},\ f_{i-2} + c_{i-2})\)—— 正是 §3 末尾那句「对最优化类，把加法换成 \(\min\) / \(\max\)」的字面实现。 它唯一的坑在目标：可以从第 0 级或第 1 级起步，也可以从倒数第二级直接跨到终点， 所以答案是 \(f_n\) 而不是 \(f_{n-1} + c_{n-1}\)，四步法的第 4 步「目标」必须单独想清楚。
另一处题库里的四道入门题¶
LC 70. 爬楼梯 与 BISHI131 数楼梯是同一个递推 \(f_i = f_{i-1} + f_{i-2}\)， 只是数据范围小得多（\(n \le 45\)），滚动两个变量即可，\(O(n)\) 时间、\(O(1)\) 空间。 它最值得记的一点是：这个数列就是斐波那契数列，只是起点错开一位。
LC 62. 不同路径与 LC 64. 最小路径和：同一张网格，一个数方案、一个求最优。 两题的状态都是「走到格子 \((i, j)\) 的答案」，转移都只从上方与左方来， 差别只在合并方式——LC62 是相加（计数），LC64 是取最小再加上当前格的代价（最优化）。 这正是计数与最优化在同一个状态空间上的对照：状态、转移、遍历顺序全都一样， 换掉的只有那个二元运算。两题都能压成一维滚动数组，\(O(mn)\) 时间、\(O(n)\) 空间。 LC62 另有一条组合数的闭式解：总共走 \(m + n - 2\) 步、其中 \(m - 1\) 步向下， 答案就是 \(\binom{m+n-2}{m-1}\)。
LC 118. 杨辉三角：状态表本身就是答案的那一类题。
递推是 \(C[i][j] = C[i-1][j-1] + C[i-1][j]\)，即组合数的加法递推，
\(O(n^2)\) 时间与空间——题面要的就是整张表，这里没有压维的余地。
逐行生成时把内层循环交给列表推导
（[1] + [a[j] + a[j+1] for j in range(len(a) - 1)] + [1]），
比双重下标赋值少一层解释开销。
7 Python 写 DP 的三条铁律¶
这三条会在后面四章反复出现，先在这里立住。
每步取模，不要最后才取¶
见 BISHI131 的坑 2。凡是计数类 DP，转移里就写 % MOD。
把最内层循环下沉到 C 层¶
这是 Python DP 优化的全部秘诀。以 01 背包的一维转移为例：
# [片段]
# 慢：Python 层循环，1e6 次迭代；倒序是为了让 f[c-v] 保持「上一轮」的值
for c in range(V, v - 1, -1):
if f[c - v] + w > f[c]:
f[c] = f[c - v] + w
# 快：整段批处理，1e6 次元素操作全在 C 层，快 5-8 倍
# 右边的候选列表在赋值前就用旧的 f 算完了，所以连倒序都不需要
f[v:] = list(map(max, f[v:], [x + w for x in f[:V + 1 - v]]))
两者等价的关键：右边的候选数组是在赋值之前用旧的 f 算好的，
所以「同一件物品不会被重复选」这个 01 语义自动成立。
这个改写贯穿 背包问题 全章， 也是
solutions/nowcoder/BISHI136/sol.py~BISHI142.py全部采用的写法。 原理见 复杂度与Python性能 §4。
树形 DP 必须迭代，不能递归¶
\(n = 2\times10^5\) 的链状树，递归深度就是 \(2\times10^5\)，setrecursionlimit 也救不了
（会爆 C 栈段错误）。见
树形 DP。
8 计数 DP 与取模¶
三种形态都可能出计数版本（把 \(\min\)/\(\max\) 换成 \(+\)）。要点：
| 要点 | 说明 |
|---|---|
| 每步取模 | 否则大整数膨胀，见本章 §7 |
| 「互不重叠 + 覆盖全部」 | 计数 DP 的正确性依据，必须显式检查 |
| 答案可能不需要取模 | BISHI144 保证答案 \(\le 10^9\)，Python 不溢出所以不用取模 |
| 最优值的方案数 | 同时维护 \(f\)（最优值）与 \(g\)（方案数）：更优则覆盖 \(g\)，相等则累加 \(g\) |
区间 / 树形 / 状压三种形态都会用到本节，它们各自的章里只留一句指回来。
9 本章速查¶
| 要点 | 结论 |
|---|---|
| DP 的两个前提 | 无后效性、最优子结构 |
| 无后效性不成立怎么办 | 把缺失的信息补进状态，不是放弃 DP |
| 设计流程 | 状态 → 转移 → 边界 → 目标，四步缺一不可 |
| 推导转移的万能技巧 | 枚举「最后一步」 |
| 计数 DP 的正确性依据 | 各类情况「互不重叠 + 覆盖全部」 |
| 计数 vs 最优化 | 同构，只差合并时用 \(+\) 还是 \(\min\)/\(\max\) |
| Python 该用哪种实现 | 递推；记忆化只在状态稀疏或顺序难定时用 |
| 记忆化的两个风险 | 递归深度、函数调用开销（慢 5–20 倍） |
| 滚动数组 | 依赖几层就留几层；也让整段 C 层批处理更容易 |
| Python 铁律 | ① 每步取模 ② 内层下沉 C 层 ③ 树形 DP 用迭代 |