記憶化：由上而下的動態規劃

一個誠實守住的習慣

上一篇導覽讓我們盯著一棵遞迴樹，它把同一個子問題重解了天文數字般多次——fib(5) 呼叫 fib(3) 兩次、fib(2) 三次，依此類推，重複次數隨樹加深而倍增。這個重複正是整個病灶，而 記憶化 正是整帖解藥。做法簡單到近乎難為情：在計算某個子問題的答案之前，先檢查你是否已經算過它；若算過，就回傳存好的值；若沒算過，就照平常的遞迴方式算出來、存下來，再回傳。遞迴的邏輯完全沒變——你只是在它旁邊多放了一本筆記。

這正是人們所說的由上而下的動態規劃。之所以叫「由上而下」，是因為你仍然從原始問題出發——fib(n)、最長路徑、最便宜的切法——讓遞迴按需求隨用隨取它所需的任何較小片段。「memoization」這個詞（沒有 r，源自 memo，給自己的便條）命名的正是那本筆記的習慣。它是進入動態規劃最溫柔的一道門，因為你保留了原本就正確的遞迴函式，只在上面栓一個快取。

memo = {}                      # the notebook, empty at the start

function fib(n):
    if n <= 1: return n        # base cases, never cached
    if n in memo: return memo[n]   # already solved? hand it back
    answer = fib(n-1) + fib(n-2)   # otherwise solve it the usual way
    memo[n] = answer               # write it down before returning
    return answer

記憶化範本：先查筆記，未命中才計算，記下，回傳。這同樣的三行幾乎能包住任何一段遞迴。

爆炸為何崩塌

下面這筆帳，讓記憶化不只是個花招。每一次對 fib(k) 的呼叫只會做兩件事之一：它是帶著那個 k 的「第一次」呼叫，那麼它做常數量的真實工作（一次加法），然後填入 memo[k]；或者它是「重複」呼叫，那麼它也只做常數量的工作（一次查表、一次回傳），不再往下遞迴。於是把所有呼叫分成兩堆。「第一次」這堆對每個相異的 k 至多一次呼叫——也就是至多 n 筆。「重複」這堆可能很大，但每次重複都是由某次第一次呼叫所發出的至多兩個遞迴請求觸發的，所以重複的次數至多是第一次的兩倍。

把兩堆相加：總呼叫數是 O(n)，而一旦你不把它委派出去的遞迴算進來，每次只做 O(1) 的工作，所以整個計算是 O(n) 時間。把它和未記憶化版本那大約 1.618^n 次的指數級呼叫相比。這巨大的改進，來自上一篇導覽點名的一個結構事實：這裡只有 n+1 個相異的子問題，fib(0) 到 fib(n)，而樸素遞迴卻為每一個付了指數次的解題費。記憶化對每個相異子問題恰好收一次費。

追蹤快取的填入

讓我們帶著筆記看 fib(5) 跑一遍，好讓節省不再抽象。第一次呼叫 fib(5) 需要 fib(4) 與 fib(3)；fib(4) 先往下鑽，需要 fib(3) 與 fib(2)；那個 fib(3) 需要 fib(2) 與 fib(1)；這條鏈在基底情況 fib(1)=1 與 fib(0)=0 觸底。當每次呼叫終於回傳時，它就記下自己的答案。關鍵在於：下一次只要任何值被請求，它早已在筆記裡，於是該請求即刻回傳，不必再次往下鑽。

沿著 fib(4) 那一側往下深鑽，會由底往上填筆記：隨著每次呼叫回傳，memo 依序得到 fib(2)=1、fib(3)=2、fib(4)=3。
現在 fib(5) 轉向它的第二個孩子 fib(3)。在樸素遞迴裡這會重新展開一整棵子樹；在這裡 memo[3] 已存著 2，所以它立刻回傳——整棵重複的子樹被剪成一次查表。
fib(5) 算出 fib(4) + fib(3) = 3 + 2 = 5，記下 memo[5]=5 並回傳。每個相異子問題 fib(0)..fib(5) 都確實只被真正計算過一次。

留意發生的事情的形狀：原本枝繁葉茂、呈指數的遞迴樹，被剪成了不比一條細路徑加上零星即時查表更大的東西。這個修剪是自動的——你從未寫程式去辨認重複；筆記檢查替你做了。這正是由上而下風格那份安靜的優雅：你以問題最自然分解的方式遞迴地描述它，而快取默默地移除冗餘。

記憶化默默假設了什麼

快取只有在「一個子問題的答案，從你存下它到你重用它之間從不改變」時才安全。這是動態規劃兩個前提中的第一個：問題必須具有重疊子問題（否則快取永遠不命中，你只是平添了開銷），而且必須具有最佳子結構（一個大問題的答案，確實是由固定的較小問題的正確答案組成的）。記憶化還重重倚賴一個藏在這兩者之中、常常沒被說出口的第三項假設：一個子問題的答案是 其引數的純函數——相同的輸入，永遠給相同的輸出。

還有一個漸進式所隱藏、屬於真實機器的但書。由上而下的記憶化會讓呼叫堆疊深到最長的依賴鏈那麼深——fib(n) 會遞迴 n 層深——所以在又長又細的遞迴上，即使它在紙上很快，仍可能讓堆疊溢位。而筆記本身也耗記憶體：O(相異子問題數) 那麼多。這些都是誠實的代價，不是致命傷，但它們正是大O時間複雜度掃到地毯底下的那類東西，也是下一篇導覽轉向由下而上替代方案的實際理由。

從數值到真正的解

如所寫的記憶化，回傳的是一個數值——最長路徑的長度、最小成本、最大價值。但你通常想要的是那個東西：哪一條路徑、哪些物品、哪些切法。光靠快取無法告訴你這些；它存的是答案，而非產生答案的選擇。標準做法是在數值填好之後重建解。你從頂層狀態出發，每一步檢視轉移所考慮過的候選選擇，問哪一個真正達到了存下的最佳值，然後沿著那個選擇進入它的子問題，再重複。

具體而言，對於 best(s) = 在各選擇 c 上取 min(cost(c) + best(next(s, c))) 的問題，重建會重新掃描狀態 s 處的各個選擇，找出右側恰等於存好的 best(s) 的那個 c，把那個 c 記為答案的一部分，然後移到 next(s, c)。因為數值已被快取，這些檢查每一個都是廉價的查表，所以重建的成本大約是沿著最佳解的狀態鏈往下走一趟——遠比原本的填表便宜。另一種做法是在每個快取值旁邊，順便存一個指向達成它的那個選擇的指標；如此一來，讀出解只是順著那些指標走，完全不必重新掃描。

在心裡把這兩個階段分開：填表階段計算每個可達狀態的最佳值（所有漸進成本都住在這裡），而重建只是 沿著一條最佳路徑 走過那些值，把見證取回來。這個切分是通用的——對下一篇導覽的由下而上風格同樣成立——而且它是思考每一個經典動態規劃最乾淨的方式，從最長共同子序列到編輯距離到背包問題皆然，本輪收尾的幾篇導覽會把它們完整走過一遍。