记忆化

记忆化是给递归“加个备忘本”：每个子问题第一次算出来就存进数组，之后再遇到直接取，避免重复计算。它是从递归通往动态规划的桥梁。

给上一节的斐波那契加记忆化：

long long f[100];
bool done[100];
long long fib(int n) {
    if (n <= 1) return n;
    if (done[n]) return f[n];     // 算过, 直接取
    done[n] = true;
    return f[n] = fib(n - 1) + fib(n - 2);   // 算一次, 存起来
}

效果立竿见影：每个 $n$ 只真正计算一次，复杂度从指数级的 $O({\phi }^n)$ 降到 $O(n)$。

坑：一是要用一个标记（done 数组，或把初值设成不可能出现的“未算”值如 $-1$）区分“算过是 0”和“还没算”，否则结果为 $0$ 的子问题会被反复重算；二是数组要开够大、下标别越界；三是记忆化本质就是自顶向下的 DP，想清楚“状态是什么、怎么转移”，改写成自底向上的循环 DP 也就水到渠成。