第 100 章 DP 入门¶
配套例题：BISHI131 数楼梯、BISHI132 小红的地砖 来源：S3
day6/DP入门.md（硬币问题、无后效性、最优子结构、数楼梯、过河卒）、day6/DP资料/基础资料/动态规划 by 余行江.md
动态规划是笔试里出现频率最高的算法族。这一章不讲任何具体模型，只讲怎么把一个问题 变成 DP——这套方法论用得熟，后面四章的模型都只是它的实例。
100.1 从贪心的失败讲起¶
S3 课件《DP 入门》的开场例子非常好，这里完整复现。
硬币问题：有面值 \(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 比暴力搜索快，是因为它把重复的子问题只算一次。
100.2 DP 的两个前提¶
一个问题能用 DP，必须同时满足两条。
无后效性¶
当前状态一旦确定，未来的决策就与「怎么走到这个状态」无关。
数楼梯里，「现在站在第 \(i\) 阶」这个状态包含了未来所需的全部信息—— 你是从 \(i-1\) 迈上来的还是从 \(i-2\) 跳上来的，对后面的走法毫无影响。所以无后效性成立。
反例：如果题目说「不能连续两次迈 2 阶」，那么「站在第 \(i\) 阶」就不够了， 未来还依赖「上一步迈了几阶」。这时要把状态加宽：
这是设计 DP 状态的核心动作：发现无后效性不成立时，不是放弃 DP， 而是把缺失的信息补进状态里。BISHI135 就是反例——它看起来需要补一维， 实际上换个坐标系就不用了，见 102-线性DP。
最优子结构¶
大问题的最优解，由子问题的最优解拼成。
凑 \(15\) 的最优方案里，如果最后一枚是 \(5\)，那么凑 \(10\) 的那部分必然也是最优的—— 否则把它换成更优的方案，总方案会更优，矛盾。
反例：求「路径上数字之和为质数」的路径。子路径的和是质数，并不能推出总和是质数， 子问题的「最优」在这里没有意义。
100.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 的关系。
100.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）。 详见 62-记忆化搜索与剪枝。
100.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 背包与完全背包。 这是全书最经典的一个细节，见 101-背包问题。
Python 里滚动数组还有一个额外好处：数组更短 ⇒ 更容易整段丢给 C 层批处理， 详见 100.7。
100.6 例题¶
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\) 用不着矩阵快速幂。矩阵加速见 104-DP优化。
题解：solutions/BISHI131.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/BISHI132.py（已通过官方样例验证）
100.7 Python 写 DP 的三条铁律¶
这三条会在后面四章反复出现，先在这里立住。
1. 每步取模，不要最后才取¶
见 BISHI131 的坑 2。凡是计数类 DP，转移里就写 % MOD。
2. 把最内层循环下沉到 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 语义自动成立。
这个改写贯穿 101-背包问题 全章， 也是
solutions/BISHI136.py~BISHI142.py全部采用的写法。 原理见 21-复杂度与Python性能 §21.4。
3. 树形 DP 必须迭代，不能递归¶
\(n = 2\times10^5\) 的链状树，递归深度就是 \(2\times10^5\)，setrecursionlimit 也救不了
（会爆 C 栈段错误）。见
103-区间树形状压DP §103.2。
100.8 本章速查¶
| 要点 | 结论 |
|---|---|
| DP 的两个前提 | 无后效性、最优子结构 |
| 无后效性不成立怎么办 | 把缺失的信息补进状态，不是放弃 DP |
| 设计流程 | 状态 → 转移 → 边界 → 目标，四步缺一不可 |
| 推导转移的万能技巧 | 枚举「最后一步」 |
| 计数 DP 的正确性依据 | 各类情况「互不重叠 + 覆盖全部」 |
| 计数 vs 最优化 | 同构，只差合并时用 \(+\) 还是 \(\min\)/\(\max\) |
| Python 该用哪种实现 | 递推；记忆化只在状态稀疏或顺序难定时用 |
| 记忆化的两个风险 | 递归深度、函数调用开销（慢 5–20 倍） |
| 滚动数组 | 依赖几层就留几层；也让整段 C 层批处理更容易 |
| Python 铁律 | ① 每步取模 ② 内层下沉 C 层 ③ 树形 DP 用迭代 |