演算法設計範式
記憶化
記憶化是這樣一個技巧：讓一個函式記住它已經算過的結果，於是重複的呼叫能立刻回傳保存好的答案，而不必把活兒重新幹一遍。這個詞源自 memo——寫給自己的備忘條。它就是「自頂向下」穿戴起來的動態規劃：你保留自然的遞迴寫法，但第一次算出某個輸入的答案時，就把它塞進一個快取（雜湊表或陣列），日後每一次對同一個輸入的呼叫都只是一次快速查表。
教科書式的例子是費氏數。樸素遞迴 fib(n) = fib(n-1) + fib(n-2) 正確卻災難性：它把同樣的值重算了指數多次，代價約為 O(2^n)。加上一個快取——遞迴前先查它，回傳前先存它——每個 fib(k) 就只算一次。執行時間隨之坍縮到 O(n)，因為只有 n 個不同的子問題、每個只解一次；你額外花 O(n) 的記憶體來存放這些答案。
當一段遞迴存在重疊子問題、而你又不想把它改寫成自底向上的迴圈時，記憶化最為出彩。它只計算你真正到達的子問題（不像填表法會把整張表填滿），當可達狀態稀疏時這會是實打實的便宜。代價是快取佔用的記憶體外加一點查表開銷；而且你必須小心地用「一切會影響答案的東西」來作快取的鍵——鍵弄錯了，它就會樂呵呵地回傳一個過時、錯誤的結果。
vector<long long> memo; // memo[i] = -1 means "not computed yet"
long long fib(int n) {
if (n < 2) return n;
if (memo[n] != -1) return memo[n]; // cache hit
return memo[n] = fib(n - 1) + fib(n - 2); // compute once, store
}
// init: memo.assign(n + 1, -1);把 O(2^n) 的樸素遞迴變成 O(n)——每個子問題恰好解一次。
記憶化（自頂向下）與填表法（自底向上）是動態規劃的兩種標準實作。記憶化不過是給遞迴加一層快取；填表法則用迭代把同樣的答案重新搭起來。當遞迴已經寫得很清楚、且只用得到部分狀態時，就選記憶化。
又稱
另見