往回看，它是第 1 章递归的直接应用；往前看，它是阶段 5 整个动态规划的入口。
很多人学 DP 卡死，是因为一上来就被灌「状态、转移方程、填表顺序」这套术语。 其实正确的顺序是：先会写递归 → 再加个数组别重复算 → 最后才是 DP。 这一章就是中间那一步。走通了，后面八章 DP 会顺理成章。
1 一句话问题
一个数字三角形，从顶上走到底下，每步只能走到正下方或右下方，求路径上数字之和的最大值。
7
3 8
8 1 0
2 7 4 4
答案 25，走法是 7 → 3 → 8 → 7输入格式：第一行 n，接下来 n 行，第 i 行有 i 个整数。
2 先用纸笔手算一遍
请照着做，这一步决定你能不能顺理成章地写出递归。
**不要从上往下想，从下往上想。**问自己：站在某个格子上，往下走能拿到的最大和是多少？
最后一行：哪儿也去不了，就是自己
2 7 4 4
倒数第二行：自己 + max(正下方, 右下方)
8 + max(2,7) = 15
1 + max(7,4) = 8
0 + max(4,4) = 4
倒数第三行：
3 + max(15,8) = 18
8 + max(8,4) = 16
顶上：
7 + max(18,16) = 25 ← 答案现在把这个手算过程写成一句话：
best(i,j)=a[i][j]+ max(best(i+1,j),best(i+1,j+1))
这就是递归。和第 1 章一样：说清职责（从 (i,j) 出发走到底的最大和）、 找到边界（最后一行就是自己）、写出递推（上面那行）。
3 暴力：把这句话直接翻译成代码
点「运行 ▶」看结果
代码几乎就是那句话的逐字翻译，思路完全正确。用样例跑一下，答案 25。
4 实测：它有多慢
点右上角的 「开始对比 ▶」。注意：30 层的三角形一共只有 30×31/2 = 465 个格子 ——
少得可怜。
本机实测，层数每加 1 暴力就翻一倍，而记忆化毫无反应：
| 层数 | 格子数 | 纯递归 | 记忆化 |
|---|---|---|---|
| 27 | 378 | 0.20 秒 | 0.003 秒 |
| 30 | 465 | 1.41 秒 | 0.003 秒 |
| 32 | 528 | 5.41 秒 | 0.003 秒 |
| 34 | 595 | 20.1 秒 | 0.003 秒 |
465 个格子的问题，暴力要跑一秒半。
这里没有什么「数据规模太大」——数据小得不能再小了。 慢的原因只有一个：它在疯狂地重复计算同一批东西。
5 慢在哪：把重复次数数出来
不要猜，直接数。下面这份代码在每次调用时给对应格子计一次数，最后把整张表打出来。
点「运行 ▶」看结果
你会看到一个杨辉三角：位置 (i,j) 恰好被调用了 C(i,j) 次。
原因很直观：从顶点走到 (i,j) 有多少条路，best(i,j) 就被完完整整地重算多少遍。
而它下面的每个格子又会因此被多算一倍…… 越往下越离谱。
具体的数字（可以自己跑出来验证）：
| 层数 n | 格子数 | 实际调用次数 | 白算的比例 |
|---|---|---|---|
| 10 | 55 | 1 023 | 94.6% |
| 20 | 210 | 1 048 575 | 99.98% |
| 30 | 465 | 1 073 741 823 | 99.99996% |
调用次数正好是 2ⁿ - 1，而格子只有 n(n+1)/2 个。
n = 20 时最热的那个格子被调用了 92 378 次 —— 每一次算出来的结果都一模一样。
6 ★ 关键的一步
best(i,j) 的值，只取决于 (i,j)。
不管你是从哪条路摸到 (2,1) 的，「从 (2,1) 出发走到底的最大和」永远是同一个数字。
它跟「你怎么来的」没有任何关系。
既然如此 —— 第一次算出来之后把它记下来，下次再问到 (2,1)，直接把记下的值还回去。
于是每个格子最多只被真正计算一次。格子一共 n(n+1)/2 个：
O(2ⁿ) → O(n²)
这一步小到让人不敢相信：算法思想没变，递归结构没变，改的只是「别重复算」。
相比暴力，代码只多了三行 —— 一个 f 数组、一个 vis 数组、一句「查表就返回」。
教科书上说 DP 要求「无后效性」，听起来很唬人。它说的就是上面那句话：
一个状态的结果，只由这个状态本身决定，和「怎么走到这个状态的」无关。
满足这一条，就能记忆化；不满足，记下来的值就是错的。 以后判断一道题能不能 DP，先问自己这一句，比背定义管用。
7 记忆化写法
点「运行 ▶」看结果
把它和 brute.cpp 并排看，差别只有开头和结尾：
long long best(int i, int j) {
if (vis[i][j]) return f[i][j]; // ← 新增：开头查表
long long res;
if (i == n - 1) res = a[i][j]; // 和暴力
else res = a[i][j] + max(best(i+1, j), best(i+1, j+1)); // 一模一样
vis[i][j] = 1; f[i][j] = res; // ← 新增：结尾存表
return res;
}不要图省事写成 vis[i][j] = 1; 放在函数开头。
这道题里放前面碰巧也对（因为状态只往下依赖，不会绕回来），但这是个坏习惯。 一旦遇到状态之间可能互相依赖的题目，「还没算完就标记成算过了」会让别人读到一个空值， 而且这种 bug 极难查。
养成习惯：开头查表 → 中间照抄暴力 → 结尾存表。 三段式，顺序别乱。
很多人图省事，不开 vis 数组，而是把 f 初始化成 -1，用 if (f[i][j] != -1) 判断算过没有。
这在本题是错的 —— 数字可以是负数，答案本身就可能等于 -1， 那个状态会被反复重算（结果仍对，但退化回指数级），更糟的题里会直接算错。
只有当你能 100% 确认某个值不可能是合法答案时，才可以拿它当哨兵。
拿不准就老老实实开一个 vis 数组，多几个字节换一个不用担心的晚上。
8 看看省掉了什么
这才 5 层就要调用 31 次。层数每加一，调用次数翻倍： n = 30 时是 2³⁰−1 = 1,073,741,823 次（十亿七千万）， 而格子一共才 465 个。慢的从来不是规模，是重复。
先看「记忆化未开启」：颜色相同的圆圈就是同一个格子。 数一数有多少个同色圆圈 —— 每一个都在把同样的东西重算一遍。
然后点「开启记忆化」。所有重复出现的节点变成灰色的「查表」小方块， 它下面那一整片子树凭空消失了。虚线是原来的树，用来对照省掉了多少。
把层数调到 6 再切换一次，省掉的比例会更吓人。 底下那行统计里，「真正算了几次」永远不会超过「三角形里的格子数」—— 这就是 O(n²) 的来历。
9 ★ 对拍验证
把「记忆化版」那一栏换成你自己默写的，再点开始。
值得一试的错误：
- 把
f初始化成 0，用if (f[i][j] != 0)判断算过没有 → 数据里有 0 时就挂 - 把
f初始化成 -1，用if (f[i][j] != -1)判断 → 生成器造了负数，会被抓 vis[i][j] = 1挪到函数开头，同时把f[i][j]的赋值删掉 → 读到空值，直接错max(best(i+1,j), best(i+1,j+1))写成max(best(i+1,j), best(i+1,j-1))→ 越界
如果数字全是正数，「每次都往大的那个方向走」这种贪心做法碰巧经常也对， 错误代码就容易蒙混过关。
加了负数之后，「眼前大」和「最终大」就分家了 —— 贪心必错，一对拍就现原形。
造数据的原则：让「错误的直觉」在你的数据上必定失败。
10 再往前一步：这就是 DP
记忆化搜索是从上往下算的：要 best(0,0)，就去问 best(1,0) 和 best(1,1)，一路递下去。
既然每个格子最终都要算一次，那干脆从下往上直接填表，连递归都省了：
// 从倒数第二行往上推
for (int i = n - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
a[i][j] += max(a[i+1][j], a[i+1][j+1]);
// 答案就是 a[0][0]**这就是动态规划。**四行，没有递归，没有 vis。
它和记忆化算的东西一模一样，只是把「用到时再算」换成了「按顺序全算一遍」。
好处是没有递归开销、不会爆栈；代价是你必须自己想清楚填表顺序
（这里是从下往上，因为 a[i][j] 依赖 a[i+1][*]）。
- 先把题意写成递归（这一步靠的是把问题说清楚，第 1 章的功夫）
- 加个数组变成记忆化（纯机械操作，没有难度）
- 想清楚依赖方向，改写成递推填表（这才是 DP）
绝大多数人卡在 DP，是因为跳过 1 和 2 直接学 3 —— 于是「状态怎么设」「方程怎么列」全靠背，题型一变就废。
遇到不会的 DP 题，永远先退回第 1 步：先写出那个会超时的递归。 写得出递归，记忆化就是免费的；记忆化能跑对，递推只是换个循环方向。
11 自测
- 洛谷 P1216 数字三角形 —— IOI1994。本章原题，先交记忆化版，再交递推版
- 洛谷 P1002 过河卒 —— NOIP2002。方案数计数，把 max 换成 +
- 洛谷 P1434 滑雪 —— 记忆化搜索的经典题。这题用递推很难写，用记忆化很自然 —— 体会一下
- 洛谷 P1255 数楼梯 —— 第 1 章那道会 TLE 的题，现在回去用记忆化解决它
你已经走完了阶段 3。第 21 章开始的阶段 5（动态规划）会大量用到这一章的思路 —— 遇到不会的 DP 题，永远先退回来写那个会超时的递归。
另外别忘了：第 1 章那道「数楼梯」（斐波那契）当时会 TLE，现在你有能力解决它了。 回去做掉它，是对这一章最好的检验。