動態規劃 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。
在函式開頭，如果快取裡已有答案就直接返回。
在每次返回前，把算出的答案存進快取。完成。