斐波那契与记忆化
记忆化把函数结果缓存，重复参数可直接查询。斐波那契递推为 fib(n) = fib(n-1) + fib(n-2)，边界是 fib(0) = 0、fib(1) = 1。朴素递归重复求解同一子问题，调用量指数增长；加入缓存后，只需求解 O(n) 个状态。
像计算员反复重算同一小计，记忆化给他一本结果簿：算一次，后续查表。本课比较朴素递归、自顶向下记忆化和自底向上填表，看三种方法如何获得相同结果。
记忆化如何工作
朴素递归是默认模式。fib(6) 调用 fib(5) 与 fib(4)，各自继续分解到 fib(1)、fib(0)。没有记录，同一个 fib(4) 子树会重建多次。
自顶向下记忆化保留递归结构，增加 memo 字典。第一次算完 fib(4) 就存储，之后用期望 O(1) 查询命中，不再展开其子树。
自底向上填表不用递归。先设 dp[0] = 0、dp[1] = 1，再依次写 dp[i] = dp[i-1] + dp[i-2]。每格只写一次，依赖的前两格已经完成。
三者结果一致：朴素法不利用重复状态，记忆化按需要计算，填表按依赖顺序主动计算。
逐步演示
默认朴素递归，n = 6，目标 fib(6) = 8。
- 调用
fib(6)：需要fib(5) + fib(4)，先进入fib(5)。 - 沿左侧深入：
fib(5) → fib(4) → fib(3) → fib(2)，到fib(1) = 1、fib(0) = 0。 - 向上合并：
combine计算fib(2) = 1 + 0 = 1，再由独立的return步骤交回结果。随后得到fib(3) = 1 + 1 = 2、fib(4) = 2 + 1 = 3、fib(5) = 3 + 2 = 5。 - 重算
fib(4)：根仍需第二个孩子。没有缓存，整个九次调用的子树重新展开，状态提示指出同参数已出现过。 - 完成：
fib(6) = 5 + 3 = 8，总计 25 次调用。
切到 Memoization，同样输入只用 11 次调用。再次请求 fib(2)、fib(3)、fib(4) 时直接查表，不再展开。切到 Bottom-up，树改为数组，填出 0, 1, 1, 2, 3, 5, 8；递推格依次聚焦、读取前两格、写入和。
树每次调用才出现一个节点；合并时两个孩子作为加数高亮，返回时结果标签使节点变绿。记忆化面板在 store 时新增行，命中时闪亮。调用计数 25 与 11 展示被省去的重复工作。
时间与空间复杂度
| 方法 | 时间，以固定成本算术计 | 空间 | 对照 |
|---|---|---|---|
| 朴素递归 | O(φⁿ)，也可用较松 O(2ⁿ) 上界 | O(n) 调用栈 | fib(6) 25 次，fib(7) 41 次 |
| 记忆化 | O(n) | O(n) 缓存与 O(n) 栈 | 每个非基础状态计算一次 |
| 自底向上 | O(n) | O(n) 表 | 只保留前两值可降为 O(1) 辅助存储 |
φ 约为 1.618。朴素调用数与斐波那契数同样指数增长；到 n = 50 时，重复调用已很多，DP 仍只处理线性数量状态。若使用任意精度整数，还需计入大整数加法和每个数的位数，表中的单位成本假设不能直接覆盖无限增长的数值。
边界情况
- n = 0、1：立即返回，不再递归。滑块从 2 开始，到 7 截止，因为朴素树已达到 41 节点。
- 基础状态不缓存：展示代码先检查
n < 2，再查 memo，因此 0、1 不作为缓存命中。 - Python
memo={}默认参数：会跨调用保留同一个字典。这里可复用，但需要独立缓存时应另行创建。 - 大 n：固定宽度整数可能先溢出，不能只看循环次数。
常见错误
- 用小输入判断朴素法可扩展。 结果正确，但指数成本在小 n 时不明显。
- 更改缓存与基础判断顺序却期待同一轨迹。 本课先处理基础状态，避免缓存它们。其他一致的实现也可正确，但会改变命中、存储和退出路径。
- 表长与边界差一位。 一般递推需要
n + 1格，循环前初始化dp[0]、dp[1]；n = 0 应单独处理，不能写越界的第二格。 - 认为记忆化改变答案。 它只减少计算量，不改变递推结果。