两次。
一次是第 17 章的记忆化搜索（数字三角形），一次是第 20 章的 coinDp.cpp
（找零钱，用来当对拍的标准答案）。它们都是货真价实的动态规划。
所以这一章不教「什么是 DP」，只补最后那一步： 把「用到时再算」的递归，翻成「按顺序全算一遍」的循环。
这一步机械得几乎没有难度 —— 除了一件事：填表的顺序。 而填错顺序的代价，是这一章唯一想让你记住的东西： 它不报错、不崩溃、不警告，只是安安静静给你一个错的答案。
1 一句话问题：爬楼梯
n 级台阶，每次能上 1 级或 2 级，一共有多少种走法？
输入 5
输出 8第 1、2 章那个「数楼梯」就是它。当时我们写出了递归，也亲眼看着它超时。现在回来把它做完。
2 先用手算一遍
| n | 走法 | 种数 |
|---|---|---|
| 0 | 站着不动 | 1 |
| 1 | 1 | 1 |
| 2 | 1+1、2 | 2 |
| 3 | 1+1+1、1+2、2+1 | 3 |
| 4 | …… | 5 |
| 5 | …… | 8 |
「一步都不走」也是一种走法 —— 这不是抠字眼，是边界必须这么定，递推才对。
如果你把 f[0] 设成 0，那 f[2] = f[1] + f[0] 就变成 1，整条链全错。
DP 的边界不是「题目的特殊情况」，是「让转移方程成立的那个起点」。
这一章后面的对拍生成器专门多造 n = 0，就是为了抓这个。
规律一眼就能看出来：f[n] = f[n-1] + f[n-2]。为什么？
看最后一步：要么是从第 n-1 级迈 1 级上来的，要么是从第 n-2 级迈 2 级上来的。
这两类互不重叠，也没有遗漏。
3 暴力：把这句话直接翻译成递归
点「运行 ▶」看结果
本机实测：
| n | 纯递归 | 递推 |
|---|---|---|
| 35 | 0.044 秒 | 0.006 秒 |
| 40 | 0.458 秒 | 0.006 秒 |
| 42 | 1.29 秒 | 0.007 秒 |
| 45 | 5.03 秒 | 0.007 秒 |
（递推那一栏还是「量不出来」：本机空跑一个 C++ 程序就要 5 毫秒左右。）
4 慢在哪：把次数数出来
耗时会随机器变，次数不会。所以直接数：
点「运行 ▶」看结果
本机跑出来的最后一行（n = 30）：
| 写法 | 算了多少次 |
|---|---|
| 纯递归 | 4 356 617 |
| 记忆化（真正算过的状态） | 30 |
| 递推（循环次数） | 29 |
十四万倍的差距，而三者算的是同一个数。
原因第 17 章已经讲透了：f(28) 被算了无数遍。
DP 的全部价值就是把「重复算」变成「算一次」。
5 ★ 关键一步：DP 三件套
写任何一道 DP，先在草稿纸上把这三句话写出来，再动手敲代码：
【1】状态：f[i] 是什么？—— 一句人话，不带任何代码。
f[i] = 走到第 i 级台阶的走法数
说不出这句话，就说明你还没想清楚，敲代码只会浪费时间。
【2】转移：f[i] 怎么从别的状态算出来？
f[i] = f[i-1] + f[i-2]
推转移的万能问法：「最后一步是什么？」 按最后一步分类， 要求这些类互不重叠（不重复计数）且没有遗漏（不漏解）。
【3】边界和顺序：起点是什么？按什么顺序填？
f[0] = 1, f[1] = 1；i从小到大。
★ 顺序不是背的，是推出来的：f[i] 依赖 f[i-1] 和 f[i-2]，
它们的下标更小 —— 所以必须先填小的。
依赖谁，就先填谁。 这一句是本章的中心，后面整章都在演示它。
6 递推：三件套翻译成代码
点「运行 ▶」看结果
盯住绿色那两格：它们永远在蓝色格子的左边。 这就是「从左往右填」的全部理由 —— 换个方向填，读到的就是空格子。
把上面代码框里的 45 改成 92，再点运行。
你会得到 -6246583658587674878。
f(91) = 7540113804746346429 已经顶到 long long 的上限，f(92) 直接溢出成负数 ——
没有任何报错。这就是第 20 章说的「对拍抓不住的那类错误」：
小数据下 int / long long 表现完全一样。
洛谷 P1255「数楼梯」要算到 n = 5000，答案有一千多位 —— 那题必须写高精度。
7 记忆化和递推，到底差在哪
到这里为止，记忆化和递推看起来完全等价：算的东西一样、复杂度一样、答案一样。
它们只有一个实质差别：递归有多深，栈就有多深。
点「运行 ▶」看结果
本机实测（默认栈 8 MB）：
| 写法 | n = 250 000 | n = 300 000 | n = 10 000 000 |
|---|---|---|---|
| 记忆化（递归） | 正常 | 段错误（崩溃） | 想都别想 |
| 递推（循环） | 正常 | 正常 | 正常（0.06 秒） |
崩掉的时候你看到的只有一句「段错误 / Segmentation fault」， 没有任何提示说是栈溢出。代码逻辑完全正确，本地小数据也测不出来 —— 这是竞赛里最难查的一类错误之一。
规矩：递归深度和数据规模同阶的时候（比如 n = 10⁵ 的线性 DP）， 要么改成递推，要么手动开大栈。
反过来，状态空间很大但实际用到的很少的时候，记忆化更划算 —— 它只算你问到的那些状态（第 17 章的滑雪就是这种）。两种写法都要会，按题选。
8 换一道题：数字三角形（第 17 章那道）
第 17 章你已经用记忆化解决过它，章末还给了四行递推。这里把那四行讲清楚：
点「运行 ▶」看结果
三件套：
- 状态：
f[i][j]= 从第i行第j列出发，走到底边能拿到的最大和 - 转移：
f[i][j] = a[i][j] + max(f[i+1][j], f[i+1][j+1]) - 边界和顺序：最后一行就是它自己；
i从大到小填 —— 因为它依赖下一行
答案是 f[0][0]，而且一个边界判断都不用写。
9 ★ 填错顺序会怎样
把外层循环从 for (i = n-2; i >= 0; i--) 改成 for (i = 0; i < n-1; i++) —— 只改一个字。
点「运行 ▶」看结果
样例三角形上：正确顺序给出 30，错误顺序给出 15。
f[i][j] 依赖 f[i+1][*]。从上往下填的时候，轮到 f[0][0] 时，
f[1][*] 还没被算过 —— 数组里存的还是输入里的原始数字。
于是 f[0][0] 拿到的是「原始的 a[1][0] 和 a[1][1]」，相当于只往下看了一层就下结论。
编译器不知道你的 f[i][j] 依赖谁 —— 那是你脑子里的东西。
所以填错顺序：不报错、不崩溃、不警告，只是答案错。
这也是为什么三件套的第三件叫「边界和顺序」，而不只是「边界」。
用第 17 章的生成器随机造 300 组三角形，263 组的答案不一样（第 3 组就出现了差异）。 剩下 37 组碰巧相等 —— 层数少的时候「只看一层」和「看到底」偶尔没区别。 又一次印证第 20 章那句话：错误的写法经常蒙对，所以蒙对不能当证据。
10 动画：三种填法并排看
下拉框里三种填法，别的什么都不用动：
- 从下往上（正确）：绿色的来源格永远已经算好；
- 从上往下（正确，但状态换了）：看每行头尾那两格 —— 它们只有一个来源，这就是要多写的
if； - 顺序写反（错的）：来源格变成红色，右下角「读到还没填的格子」一路涨。
11 同一道题，换个状态换个方向
点「运行 ▶」看结果
注意这里的状态定义变了：g[i][j] 是「从顶点走到这一格的最大和」，
和 triDown.cpp 的「从这一格走到底边」完全是两回事。
代价有两个：
- 边界要单独伺候：每行最左只能从正上方来，最右只能从左上方来 —— 两个
if； - 答案要多扫一遍：终点是底边任意一格，得取最大值。
同一道题可以有好几种状态定义，选哪个决定了后面全部的难度。
triDown 一个 if 都不用写，triUp 要写两个还要多扫一遍 —— 而它们解的是同一道题。
所以设状态的时候多花三分钟，问自己： 哪个方向的边界更少？哪个方向的答案更直接（是某一个固定格子，还是要再扫一遍）？ 选错不会错，但会让你多写一倍的代码，也多一倍出错的机会。
12 ★ 对拍：直接用第 17 章的暴力和生成器
数字三角形的输入输出格式和第 17 章一模一样，所以标准答案（那份 2ⁿ 暴力） 和生成器一个字都不用改，直接拿过来用。
这不是偷懒 —— 这正是「标准答案要用完全不同的思路」的最好实现： 第 17 章那份暴力是枚举所有路径，和这里的递推填表毫无关系。
爬楼梯也来一台（标准答案是纯递归）：
值得故意写错、看对拍怎么抓的：
f[0]写成 0 → 只要生成器造出n = 0或n = 2就立刻被抓- 循环从
i = 1开始（漏了f[1]的边界）→ 被抓 - 数字三角形的循环方向写反 → 被抓（而且 300 组里有 263 组会被抓）
long long写成int→ 对拍抓不住（小数据不溢出），只能靠脑子
13 拿到一道 DP 题，按这个顺序做
- 先写出会超时的递归。（第 17 章反复强调过：写不出递归就别想 DP。）
- 加一张表变成记忆化。 纯机械操作，没有难度。
- 把三件套写在草稿纸上：状态是什么（一句人话）、转移怎么来（问「最后一步是什么」）、 边界和顺序（依赖谁就先填谁）。
- 翻成递推循环。 循环方向由第 3 步的依赖方向决定，不是背的。
- 对拍。 标准答案用暴力或记忆化 —— 反正你第 1 步已经写好了，白捡一个。
卡在第 3 步是正常的，那说明状态设错了 —— 回到第 1 步，看看递归函数的参数是什么， 那几个参数通常就是状态的维度。
转移、边界、顺序都是有章可循的机械活。真正难的永远是第一件：状态是什么。
接下来六章就是在练这一件事：
- 第 22 章：状态里塞一个「以 i 结尾」（最长上升子序列）
- 第 23、24、25 章：状态多一维「容量 / 费用」（背包）
- 第 26 章：状态是一段区间（石子合并）
- 第 27 章：状态挂在树的节点上（树形 DP）
- 第 28 章：状态是一个集合，压成一个整数（状压 DP）
每一章的新东西都只有「状态长什么样」，其余三件套的用法一模一样。
14 自测
- 洛谷 P1216 数字三角形 —— IOI1994。本章原题，先交记忆化版再交递推版，对比一下提交记录里的用时和内存
- 洛谷 P1255 数楼梯 —— 爬楼梯的原题，但 n 到 5000 —— 答案上千位，必须写高精度。递推部分你已经会了，这题练的是高精度加法
- 洛谷 P1002 过河卒 —— NOIP2002。二维递推，把 max 换成 +（计数）。注意马的控制点和边界，以及 long long
- 洛谷 P1044 栈 —— NOIP2003。卡特兰数。状态不好设 —— 先老实写搜索，再从搜索里找状态，正是本章第 13 步那套流程
- 洛谷 P1077 摆花 —— NOIP2012。状态要开二维（第几种花、已经摆了几盆），是通向第 23 章背包的过渡题
第 22 章：最长上升子序列，O(n²) → O(n log n)。
它的状态是「以 i 结尾的最长上升子序列长度」—— 「以某个位置结尾」是 DP 里最常用的状态设法之一，这一章会把它讲透。
而那个 O(n log n) 的优化会用到第 8 章的二分查找 ——
到时候你会看到一个漂亮的事实：那个用来二分的数组，天然就是单调的。