第 15 章 动态规划
本章解决的问题：同一个子问题被反复算了上百万次，怎么用一张表把它救回来？以及"状态"到底该怎么定义 —— 为什么只改一个词，答案就从全对变成全错？
15.1 从暴力递归到记忆化
学习目标：学完本节，你能
- 识别重叠子问题 —— 看清一个递归里"同一个子问题被算了多少次"；
- 用记忆化（加一张表、两行代码）把暴力递归救回来，并说清它为什么有效；
- 说清 动态规划与分治的分界：子问题重不重叠；
- 对比自顶向下与自底向上两种写法，说出各自的取舍。
先修：2.1（递归的两个条件）、2.4（分治）、14.3（贪心失效、该转向 DP 的信号）。 固定术语：动态规划（Dynamic Programming, DP）、记忆化（Memoization）、重叠子问题。 环境与版本：.NET 8 / C# 12。 预计阅读：32 分钟。
一、直觉：一个算了 1140 万次的问题
2.1 节埋过一颗种子：
static long Fib(int n)
{
if (n <= 1) return n;
return Fib(n - 1) + Fib(n - 2);
}
三行代码，完全正确，但它慢得离谱 —— 2.1 节实测 Fib(35) 调用了 2986 万次。
小陈当时的反应是："不就是斐波那契吗？我循环写三行就出来了。"
他说得对。但这一节要讲的不是斐波那契。
斐波那契只是一个"标本" —— 它身上有一个几乎所有"看起来能递归、但一跑就爆"的问题都会有的毛病：
同一个子问题，被反复算了一遍又一遍。
14.3 节结尾说过：贪心失效之后，下一步是把"一条路"扩展成"所有路"。 而"所有路"写出来的第一版，通常就是这种暴力递归 —— 正确，但慢到不能用。
这一节要做的，就是给这个慢找出原因，然后用两行代码修好它。
二、形式化：重叠子问题
先把"慢在哪"看清楚。Fib(5) 的递归调用树：
Fib(5)
/ \
Fib(4) Fib(3) <- Fib(3) 出现第 1 次
/ \ / \
Fib(3) Fib(2) Fib(2) Fib(1) <- Fib(3) 出现第 2 次
/ \ / \ / \
Fib(2) Fib(1) F(1) F(0) F(1) F(0) <- Fib(2) 出现了 3 次
/ \
F(1) F(0)
数一数：Fib(3) 算了 2 次，Fib(2) 算了 3 次 —— 而它们的结果每次都一样。
重叠子问题（Overlapping Subproblems）：在递归的过程中，同一个子问题被反复求解。
它的直接后果是：递归树里出现了大量【完全相同的子树】，算法在做纯粹的重复劳动。
一个关键的分界
这是动态规划和分治最重要的区别：
| 分治（2.4 节） | 动态规划 | |
|---|---|---|
| 子问题 | 互不重叠 | 大量重叠 |
| 例子 | 归并排序、快速幂 | 斐波那契、背包、找零 |
| 递归树的形状 | 一棵真正的树，节点数 = 工作量 | 一棵被压扁的树，实际不同的子问题很少 |
| 要不要缓存 | 不要 —— 没东西可缓存 | 要 —— 这正是提速的全部来源 |
归并排序的左右两半是不相交的（左边排完排右边），所以没有重复计算，缓存也没用。
斐波那契的左右两支大量交叉（都要算
Fib(n-2)），所以缓存一下就能省掉绝大部分工作。
那么"重叠"到底有多严重？下一节数给你看。
三、实测一：重叠到底有多严重
给朴素递归加一个计数器，逐个子问题统计调用次数：
朴素递归 Fib(33) = 3,524,578
总调用次数：11,405,773
不同的子问题：34 个（就是 Fib(0) ~ Fib(33)）
耗时：16.0 ms
先看这两个数的对比：
1140 万次调用，而不同的子问题只有 34 个。
平均每个子问题被算了 335,464 次。
再看分布：
子问题 调用次数 占总调用
-------- ------------ --------
Fib(1 ) 3,524,578 30.9%
Fib(2 ) 2,178,309 19.1%
Fib(5 ) 514,229 4.5%
Fib(10 ) 46,368 0.4%
Fib(20 ) 377 0.0%
Fib(33 ) 1 0.0%
调用最多的子问题：Fib(1)，被调用了 3,524,578 次 —— 而它只需要算【一次】。
这张表有一个清晰的规律：
越"小"的子问题，被重复得越厉害 ——
Fib(1)30.9%、Fib(2)19.1%，两者加起来占了一半的调用。而
Fib(33)自己只被调用了一次（它是根节点）。这就是为什么"加缓存"能救它：**真正需要计算的只有 34 个值， 另外那 1140 万次调用全是在重复）。
四、记忆化：只加两行
修法简单到有点不像话：
long[] memo = new long[n + 1];
Array.Fill(memo, -1); // -1 表示「还没算过」
long Fib(int n)
{
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // ★ 算之前先查表
return memo[n] = Fib(n - 1) + Fib(n - 2); // ★ 算完把结果写进表
}
记忆化（Memoization）：把已经算过的子问题结果存起来，下次遇到直接返回。
就这两行：
| 行 | 作用 |
|---|---|
if (memo[n] != -1) return memo[n]; |
算之前先查表 —— 算过就直接拿走 |
return memo[n] = ... |
算完写进表 —— 供以后使用 |
注意递归的结构【一个字没改】 —— 还是
Fib(n-1) + Fib(n-2)， 只是把"直接算"改成了"先查表，没有再算"。
五、实测二：记忆化的效果
记忆化递归 Fib(33) = 3,524,578（和朴素版一致：True）
函数被调用次数：65
其中【真正计算】的次数：32
耗时：0.043 ms
三个数字对比：
总调用次数： 朴素 11,405,773 -> 记忆化 65 （175,473 分之 1）
实际计算次数：朴素 11,405,773 -> 记忆化 32 （356,430 分之 1）
三个数分开读：
| 数字 | 含义 |
|---|---|
| 65 次调用 | 从 1140 万降到 65 —— 只有原来的十七万分之一 |
| 32 次真正计算 | 每个子问题恰好算一次（Fib(2) 到 Fib(33)，共 32 个） |
| 结果完全一致 | True —— 提速没有改变任何答案 |
65和32这两个数为什么不一样？因为"被调用"不等于"被计算"：第一次调用
Fib(k)时算并存表，之后再调到它，直接在查表那一步就返回了。32 次计算 = 32 个不同的子问题，一次不重复 ✓ —— 这正是记忆化的目标。
0.043 ms vs 16.0 ms —— 快了约 370 倍，而且这是在小规模（n=33）上的对比。n 越大，差距越夸张 （朴素递归是指数级的，记忆化是线性的）。
⚠️ 但要注意一个细节：这里比的是"耗时"，而耗时受机器影响。
真正与机器无关的那两个数是 11,405,773 和 65 —— 它们在任何电脑上跑都是这两个值（1.2 节、1.3 节的同一条原则）。
六、自顶向下 vs 自底向上
记忆化是最省事的改法（保留递归结构），但它不是唯一的写法。
同一件事还有另一种写法：不递归，直接从最小的子问题往上推。
static long BottomUp(int n)
{
var dp = new long[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2]; // 直接用已经算好的更小的问题
return dp[n];
}
两种写法的名字：
| 自顶向下（Top-Down） | 自底向上（Bottom-Up） | |
|---|---|---|
| 写法 | 递归 + 缓存（记忆化） | 循环 + 表（递推） |
| 顺序 | 从大问题往下拆，用到才算 | 从小问题往上填，全都算 |
| 这节的代码 | Fib(n-1) + Fib(n-2) 加两行 |
dp[i] = dp[i-1] + dp[i-2] |
它们是同一个东西的两面：自顶向下的"缓存表"，就是自底向上的"dp 表" —— 区别只在于"谁先被填上"。
取舍：
| 维度 | 自顶向下 | 自底向上 |
|---|---|---|
| 改动量 | 小 —— 暴力递归加两行 | 要把递归改写成循环 |
| 算哪些状态 | 只算用到的 | 全都要算 |
| 递归开销 | 有（函数调用） | 无 |
| 栈深度风险 | 有 —— 递归多深栈就多深（2.2 节：一万多层就崩） | 无 |
| 能否做空间优化 | 不方便 | 可以（滚动数组，15.4 节） |
"只算用到的"这条听起来很美，但它什么时候真的有用？
当状态空间很大、而你只需要其中一小部分时。
斐波那契恰好相反 —— 每个子问题都要用到，自顶向下省不掉任何一个，还白白多付了递归的开销。
七、实测三：三个版本的正面对比
算 Fib(90)（这个规模朴素递归已经不可能跑完了）：
每种实现各跑 10,000 次取总耗时，10,000 次里只测一次分配量：
实现 结果（算一次） 10,000 次耗时 单次分配
------------------------ -------------------- ---------- --------
自顶向下（记忆化递归） 2,880,067,194,370,816,120 6.4 ms 752 B
自底向上（数组） 2,880,067,194,370,816,120 2.1 ms 752 B
自底向上（滚动变量） 2,880,067,194,370,816,120 1.4 ms 0 B
三者结果一致：True
记忆化递归比滚动变量慢 4.4 倍，而且每算一次就要分配 752 字节。
这张表要横着看，也要竖着看：
横着看：三种写法的结果一模一样（
True）—— 它们算的是同一个东西，只是路径不同。竖着看：耗时 6.4 → 2.1 → 1.4 ms，内存 752 → 752 → 0 字节。
第三行的"0 字节"值得单独说：
static long Rolling(int n)
{
if (n <= 1) return n;
long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
return b; // 只留最近两个值
}
它连表都不要了 —— 因为
Fib(i)只依赖Fib(i-1)和Fib(i-2)， 再往前的那些值算完就永远用不到了。这就是"空间优化"的最简单形态（15.4 节会专门讲它的适用边界）。
⚠️ 但"滚动变量"不是万能的：它成立的前提是"状态依赖只有固定几步"。
换成 0/1 背包那种"依赖上面一整行"的问题，就滚不动了（15.4 节细讲）。
所以这一节的结论很干脆：
| 场景 | 推荐 |
|---|---|
| 想快速把暴力递归救活 | 记忆化（改动最小，两行） |
| 每个状态都要算，且 n 可能很大 | 自底向上（无递归开销、无栈风险） |
| 状态依赖只有固定几步 | 自底向上 + 滚动变量（连表都省了） |
八、练习
练习 15.1.1（手画调用树）
对 Fib(5)：
(a) 画出完整的递归调用树，标出每个节点。
(b) 数一数 Fib(2)、Fib(3) 各被调用了多少次。
(c) 如果加记忆化，实际会计算几次？省掉了多少次？
练习 15.1.2（判断） 判断对错并说明理由： (a) 所有递归都能用记忆化加速。 (b) 记忆化把指数级的算法变成了线性的算法。 (c) 自底向上一定比自顶向下快。 (d) 记忆化的递归不会栈溢出。
练习 15.1.3（识别重叠） 下面几个递归问题，哪些有重叠子问题？说明理由。
(a) 归并排序（每次把数组对半分）
(b) 快速幂（power(x, n) 递归成 power(x, n/2) 的平方）
(c) 爬楼梯（每次走 1 级或 2 级，问有几种走法）
(d) 二叉树的前序遍历
练习 15.1.4（写记忆化）
给定一个二维网格，从左上角走到右下角，每次只能向右或向下走一格，问有多少条路径。
（朴素递归：paths(r, c) = paths(r-1, c) + paths(r, c-1)）
(a) 朴素递归的时间复杂度是多少？为什么？ (b) 用记忆化改写，关键代码是什么？ (c) 记忆化之后的复杂度是多少？状态一共多少个？
练习 15.1.5（挑战·记忆化的边界） 记忆化有一个"看起来很明显、实际很容易踩"的坑：缓存必须跟着参数走。
(a) 如果 Fib 改成"带取模"的版本（Fib(n) % 1000000007），缓存还能直接存 Fib(n) 吗？
(b) 如果一个递归函数有两个参数 f(a, b)，缓存该是什么形状？
(c) 反例：什么情况下，"缓存结果"会给出错误的答案？（提示：想想函数的返回值是否只由参数决定）
九、练习答案
15.1.1
(a) Fib(5) 的完整调用树
Fib(5)
/ \
Fib(4) Fib(3)
/ \ / \
Fib(3) Fib(2) Fib(2) Fib(1)
/ \ / \ / \
Fib(2) Fib(1) F(1) F(0) F(1) F(0)
/ \
F(1) F(0)
(b) 调用次数
| 子问题 | 调用次数 |
|---|---|
Fib(5) |
1 |
Fib(4) |
1 |
Fib(3) |
2 |
Fib(2) |
3 |
Fib(1) |
5 |
Fib(0) |
3 |
总共 15 次调用（Fib(1) 已被当作基准情形，不再往下展开）。
(c) 加记忆化后只需要计算 6 次（Fib(0) 到 Fib(5)，每个一次）。
省掉了 15 − 6 = 9 次。
注意 n=5 时只省了 9 次，看起来不起眼 —— 但增长是指数的： 本节实测 n=33 时省掉了 1140 万次里的绝大部分（只剩 32 次计算）。
15.1.2
| 小题 | 判断 | 理由 |
|---|---|---|
| (a) | ❌ 错 | 只有带【重叠子问题】的递归才能受益。 归并排序、二分查找这类子问题互不重叠的，缓存了也用不上（没有重复调用）。 |
| (b) | ✅ 对（当子问题确实重叠时） | 斐波那契：朴素 $O(2^n)$ → 记忆化 $O(n)$。但前提是"不同的子问题只有多项式个" —— 如果状态数本身就是指数的，记忆化也救不了。 |
| (c) | ❌ 错 | 取决于"是否需要算全部状态"。 本节实测：斐波那契上自底向上更快（2.1 vs 6.4 ms），但如果状态空间大、只用到一小部分，自顶向下反而省。 |
| (d) | ❌ 错 | 记忆化不改变递归深度。 本节示例里 Fib(n) 的递归深度仍然是 $n$ —— n 大到一定程度照样栈溢出（2.2 节的教训）。要用自底向上才能彻底规避。 |
(d) 是最容易踩的一条：记忆化解决的是"重复计算"，不是"递归太深" —— 两个问题，两套解法。
15.1.3
| 问题 | 有没有重叠 | 理由 |
|---|---|---|
| (a) 归并排序 | ❌ 没有 | 左右两半是不相交的区间 —— 排完左边排右边，任何一段都不会被排两次。这是 2.4 节说的"分治"。 |
| (b) 快速幂 | ❌ 没有 | power(x, n) 只递归一次（power(x, n/2)），递归树是一条链，每个规模只出现一次。 |
| (c) 爬楼梯 | ✅ 有 | ways(n) = ways(n-1) + ways(n-2) —— 和斐波那契结构完全相同，ways(n-2) 会被算两次。 |
| (d) 二叉树前序遍历 | ❌ 没有 | 每个节点恰好被访问一次 —— 它压根不是"把问题拆成子问题"的结构。 |
一个快速判据：看递归式右边有没有【重复出现同一个规模】。
T(n-1) + T(n-2)→ 重了（n-2会被两条分支都碰到）✓ 需要记忆化T(n/2)（只有一项）→ 不重T(n/2) + T(n/2)但两半内容不相交（归并）→ 计算量翻倍但没有重复计算
15.1.4
(a) 朴素递归是指数级的。
为什么？ 每次递归分成两支，递归深度是 $r + c$（每步不是减一行就是减一列）， 所以调用次数是 $O(2^{r+c})$。
而且大量子问题重复：paths(1,1) 会被 paths(2,1) 和 paths(1,2) 各调用一次，
再往上还会被更多次调用 —— 和斐波那契是同一个形状。
(b) 记忆化的关键代码
long[,] memo = new long[rows, cols];
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
memo[i, j] = -1;
long Paths(int r, int c)
{
if (r == 0 || c == 0) return 1; // 第一行/第一列只有一条路
if (memo[r, c] != -1) return memo[r, c]; // ★ 查表
return memo[r, c] = Paths(r - 1, c) + Paths(r, c - 1); // ★ 存表
}
注意缓存的形状：函数有两个参数
(r, c)，缓存就是二维的 —— 缓存的维度必须和参数的个数一致（这正是练习 15.1.5(b) 问的）。
(c) 记忆化后是 $O(r \times c)$，状态一共 $r \times c$ 个。
因为每个 (r, c) 组合只会被真正计算一次，而参数的所有可能取值就是 $r \times c$ 种。
从 $O(2^{r+c})$ 到 $O(r \times c)$ —— 这就是记忆化的力量，也解释了为什么它能"把指数变成多项式"。
15.1.5
(a) 能，而且更该缓存。
Fib(n) % MOD 完全由 n 决定（参数相同，结果一定相同），所以缓存是合法的。
而且取模之后更应该缓存：
| 不取模 | 取模 | |
|---|---|---|
| 数值大小 | $n > 92$ 就溢出 long |
永远小于 $10^9$ |
| 需要缓存吗 | 要 | 更要 —— 它是唯一能在 n 很大时算下去的办法 |
编程题里"答案对 $10^9+7$ 取模"这个约定，一半的原因是防止溢出，另一半是让 DP 在大 n 上可行。
(b) 缓存要和参数一一对应。
两个参数 f(a, b) → 二维表：
long[,] memo = new long[maxA + 1, maxB + 1];
三个参数就三维，依此类推。
这就是 15.4 节"空间优化"要处理的问题： 维度一多，表就爆炸（比如 $1000^3$ = 10 亿个格子）—— 所以要想办法把"其实用不到的那些格子"砍掉。
(c) 当函数的返回值【不只由参数决定】时。
反例：
int counter = 0;
int F(int n)
{
counter++; // ← 副作用：每次调用都改外部状态
return n + counter;
}
F(5) 第一次调用返回 6，第二次可能返回 7 —— 参数相同但结果不同，缓存就会给出错误答案。
更常见的隐蔽版本：
| 情形 | 为什么缓存会错 |
|---|---|
| 函数读了外部可变变量 | 比如读了一个全局配置，而配置在两次调用之间被改了 |
| 函数依赖随机数或时间 | 参数相同，结果不同 |
| 状态里含"已经做了哪些选择" | 比如 14.1 的满减券：同样是"剩余金额 50"，可用券的集合可能不同 |
最后一条正是 14.1 练习 14.1.4 里那个坑： "当前订单金额"单独作为状态是不够的 —— 还得知道"哪些券已经用过了"。
状态定义得不对，DP 就会给出错误答案 —— 这是 15.2 节的主题。
十、常见错误
| 误区 | 纠正 |
|---|---|
| 认为"所有递归都能用记忆化加速" | 只有子问题【重叠】时才有用。 归并排序、二分查找的子问题互不重叠，缓存了也白搭。 |
| 认为记忆化能解决递归太深的问题 | 它解决的是"重复计算"，不是"递归深度"。 记忆化的 Fib(n) 递归深度还是 $n$，该栈溢出照样溢出。 |
| 缓存存了"参数相同但结果不同"的东西 | 缓存的合法性要求"返回值只由参数决定"。 读了外部可变状态、依赖随机数、或状态定义不全，都会错。 |
| 以为自底向上"一定更快" | 要看是否需要算全部状态。 本节实测斐波那契上是（2.1 vs 6.4 ms），但状态空间大而稀疏时自顶向下更省。 |
| 混淆"分治"和"动态规划" | 分治的子问题不重叠，DP 的重叠 —— 这是两者最本质的区别（第二节的表）。 |
| 缓存维度写少了 | 参数有几个，表就有几维。 两个参数写成一维数组，会互相覆盖。 |
| 只报耗时，不报操作次数 | 耗时受机器影响。本节的两个关键数是 11,405,773 和 65 —— 它们在任何机器上都一样。 |
十一、本节总结
- 重叠子问题：递归树里同一个子问题被反复求解。这是 DP 与分治的分界线 —— 分治的子问题不重叠，DP 的重叠。
- 实测一（本节的量化）：
Fib(33)朴素递归调用 11,405,773 次，而不同的子问题只有 34 个 —— 平均每个子问题被算了 335,464 次。调用最多的是Fib(1)（352 万次，占 30.9%）。 - 记忆化只加两行：算之前先查表、算完把结果写进表。递归结构一个字不改。
- 实测二：调用次数 11,405,773 → 65（十七万分之一），真正计算 32 次（每个子问题恰好一次），结果完全一致。
- 自顶向下 vs 自底向上：前者是"递归 + 缓存"，后者是"循环 + 表"。它们是同一个东西的两面 —— 缓存表就是 dp 表，区别只是"谁先被填上"。
- 实测三：
Fib(90)上三者耗时 6.4 / 2.1 / 1.4 ms，内存 752 / 752 / 0 字节 —— 滚动变量连表都省了（因为Fib(i)只依赖前两个）。 - 取舍：想快速救活暴力递归 → 记忆化；每个状态都要算且 n 可能很大 → 自底向上；依赖只有固定几步 → 滚动变量。
- 记忆化的边界：返回值必须只由参数决定。读了外部可变状态、依赖随机数、或状态定义不全，缓存就会给错答案 —— 后者正是 15.2 节要解决的。
下一节衔接：本节用一个"修好的斐波那契"演示了记忆化，但斐波那契有个特点：它的状态就是一个整数 $n$ —— 参数是什么，状态就是什么，不用动脑子。
真正的问题来了：面对一个新问题，你怎么知道该拿什么当"状态"？
比如那个满减券的组合问题（14.1 练习 14.1.4、14.3 练习 14.3.4）： "当前订单金额"够不够当状态？如果不够，还缺什么？
15.2 节回答这个问题 —— 它会给出一套定义状态的自检问题，而那是动态规划里最容易翻车的一步。
状态外显
{
"book": "数据结构与算法自学：从工程直觉到复杂度思维",
"section": "15.1",
"title": "从暴力递归到记忆化",
"covered": [
"从 2.1 节的 Fib(35) 引出「同一个子问题被反复算」这个毛病",
"重叠子问题的定义与 Fib(5) 的调用树演示",
"「分治 vs DP」的分界：子问题重不重叠（含四种递归式的判别）",
"实测一：Fib(33) 总调用 11,405,773 次 vs 34 个不同子问题，逐个子问题的调用分布",
"记忆化的两行代码（查表 + 存表）与其原理",
"实测二：调用次数 11,405,773 -> 65、真正计算 32 次、结果一致",
"自顶向下 vs 自底向上的概念对照与五个维度的取舍表",
"实测三：Fib(90) 三个版本的耗时（6.4/2.1/1.4 ms）与分配量（752/752/0 字节）",
"滚动变量的原理（状态依赖只有固定几步）与其边界",
"记忆化的合法性边界（返回值必须只由参数决定）"
],
"unresolved": [
"状态定义的系统方法留到 15.2",
"0/1 背包的 DP 留到 15.3",
"空间优化（滚动数组）留到 15.4",
"树形/图上的 DP（如象棋状态搜索）超出本书范围"
],
"canonical_terms": {
"动态规划（Dynamic Programming, DP）": "通过保存子问题结果、避免重复计算的算法设计方法；前提是最优子结构与重叠子问题",
"记忆化（Memoization）": "自顶向下的 DP：递归 + 缓存，算之前先查表、算完把结果写进表",
"重叠子问题（Overlapping Subproblems）": "递归过程中同一个子问题被反复求解；DP 与分治的分界线"
},
"symbols_units": {
"n": "输入规模",
"memo[k] / dp[k]": "子问题 k 的结果",
"MOD": "取模常数（本节练习中为 10^9+7）"
},
"assumptions": [
"读者已掌握 2.1 的递归与 2.4 的分治",
"读者理解 2.2 的栈深度限制",
"斐波那契只作为「标本」使用，正文已说明它的实际最优解法是 O(1) 的迭代"
],
"word_count_actual": 2982,
"checks": [
"C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
"项目文件：99-tools/samples/Ch15/Sec151/",
"实验一：Fib(33) 总调用 11,405,773、34 个不同子问题、Fib(1) 被调用 3,524,578 次（30.9%），均为实测",
"实验二：记忆化后调用 65 次、真正计算 32 次、耗时 0.043 ms，为实测",
"实验三：Fib(90) 三版本 6.4/2.1/1.4 ms、分配 752/752/0 字节，为实测（每项跑 10000 次取 3 轮最快）",
"术语写法与 glossary.md 一致（动态规划、记忆化、重叠子问题）"
],
"known_issues": [
"实验三初版用 Fib(80) 且只跑一次，三个版本的耗时全是 0.000 ms（Stopwatch 精度不够）—— 改为 Fib(90) 并重复 10000 次取总耗时，才拉开 6.4/2.1/1.4 的差距",
"初版加了一个「爬楼梯 + 坏台阶」的补充实验，想展示「自顶向下只算需要的状态」的优势，但那个例子（第 5、6、7 级坏掉）算出来是【0 种走法】（从 4 到 8 必须踩到坏的），例子失去意义；改为在正文里用一段文字说明取舍，并删掉该实验",
"局部函数递归需要捕获外部变量（callCount/memo 等），因此不能用 static 局部函数 —— 代码里全部改用非 static 形式"
],
"next": "15.2 状态定义与转移方程"
}