动态规划 I：记忆化

同样的活，干了一百万遍

回想斐波那契数：每一个都是前两个之和。教科书式的递归自己就写出来了：`fib(n) = fib(n-1) + fib(n-2)`。干净又正确——却慢得灾难性。原因在于，同样的子问题被一次又一次地重算。把 `fib(5)` 的调用树画出来，你会看到 `fib(2)` 被*分别从头算了三遍*。

                       fib(5)
                      /       \
                 fib(4)        fib(3)
                /     \        /     \
           fib(3)   fib(2)  fib(2)  fib(1)
           /    \
       fib(2)  fib(1)        <- fib(2) appears 3 times total,
                                fib(3) appears twice ... and it
                                doubles with every step of n.

朴素递归树每次调用分两个叉，所以它的规模按 2^n 增长。那是 O(2^n)——n=50 时大约是一千万亿次调用。

有两条性质让这件事可以修，而它们合在一起，正是一个[[dynamic-programming|动态规划]]问题的标志。第一，重叠子问题：同样的更小问题反复出现（那个被重复的 `fib(2)`）。第二，最优子结构：大问题的答案，是直接由更小问题的答案搭起来的。当你两者都看到，你手上就是一道 DP 题了。

记忆化：把答案写下来

[[memoization|记忆化]]是最简单的修法，而且它让你那段漂亮的递归代码几乎原封不动。你加一个缓存——一个地方，在你第一次算出每个答案时把它存起来。然后每次调用只多做两件事：*开工前先查缓存*，以及*返回前先存结果*。这就是全部的把戏。

#include <vector>

long long fib(int n, std::vector<long long>& memo) {
    if (n <= 1) return n;                 // base cases
    if (memo[n] != -1) return memo[n];    // 1) cache hit: reuse
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);  // 2) store
    return memo[n];
}

long long fib(int n) {
    std::vector<long long> memo(n + 1, -1);  // -1 = "not computed yet"
    return fib(n, memo);
}

加上的这两行把 O(2^n) 变成了 O(n)：每个 fib(k) 只算一次，此后永远由 memo[k] 供应。

为什么是 O(n)？因为只有 `n+1` 个不同的子问题（`fib(0)` 到 `fib(n)`），而缓存保证每个*真正被计算*的只有一次——之后的每一次请求都是瞬时查表。我们用一点内存（那个数组）换来了天文数字般的时间。这个交易——以空间换时间——是每一个 DP 的核心。

当状态不是一个普通整数

当子问题由一个小整数标识时，数组缓存就够用。但很多时候，状态——那一束钉死一个子问题的值——是别的东西：一对 `(i, j)`、一个字符串、一个位置加一份预算。当一个普通下标搞不定时，就用哈希表：`std::unordered_map`。键，就是任何能唯一指认这个子问题的东西。

#include <unordered_map>
#include <string>

std::unordered_map<std::string, long long> memo;

long long solve(int i, int j) {
    std::string key = std::to_string(i) + "," + std::to_string(j);
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;   // cache hit

    long long result = /* ... combine subproblems of (i,j) ... */ 0;
    memo[key] = result;                         // store before returning
    return result;
}

同样的两步仪式——先查，再存——只是用一个编码了完整状态 (i, j) 的字符串作键。模式从不改变。

记忆化，一步一步来

这就是你可以自顶向下套用到任何 DP 题上的完整配方。请注意，它无非就是「写出诚实的递归，再给它装上一个缓存」。你不必去操心东西被计算的顺序——递归会替你把它理清楚。

先写出朴素的递归：基准情形，然后「答案 = 组合（更小的答案）」。
确定状态——指认一个子问题所需的最少的值。那就是你的缓存键。
建一个缓存：状态是小整数就用数组，否则用 unordered_map。
在函数开头，如果缓存里已有答案就直接返回。
在每次返回前，把算出的答案存进缓存。完成。