记住算过的

上一节我们从小往大填数组，其实还有一种保留递归写法的提速办法：记忆化。思路很朴素——算过的结果记在本子上，下次要用先查本子，查到直接返回，查不到才真去算。

long long f[100];            // 全局，初值 0 表示"还没算过"
long long fib(int n) {
    if (n <= 2) return 1;
    if (f[n]) return f[n];   // 查到笔记，直接用
    return f[n] = fib(n-1) + fib(n-2);
}

关键在 if (f[n]) return f[n];：它把原本指数级的重复调用剪成每个 $n$ 只真算一次，时间从 $O(2^n)$ 降到 $O(n)$。

这就是"记忆化搜索"，DP 的另一副面孔：从大往小递归，但用数组缓存挡住重复。坑：用 f[n] 判空只在真实答案不为 0 时才对；若答案可能为 0，要另开一个 bool 算过没 数组标记，别把 0 误当成"没算过"。