由上而下的記憶化（top-down memoization）
/ memoization = MEM-oh-ization (no r) /
你寫下最直觀的遞迴解法——那種藉由詢問自己較小版本來解題的寫法——但你給它一本筆記本。函式每次算完某個輸入的答案，就把答案抄在那個輸入旁邊。每次被要求一個答案時，它先翻筆記本：若答案已經在那兒，就立刻回傳，不再重算。那本筆記本就是記憶表，這個技巧就叫記憶化。它保留了自然好讀的遞迴結構，卻消滅了重複的工作。
具體來說，記憶化函式的虛擬碼長這樣：function solve(state)：若 memo[state] 已填，回傳 memo[state]；若 state 是基底情況，回傳其已知值；否則藉由組合 solve(較小的 state) 算出答案，存入 memo[state] 再回傳。每個相異狀態第一次被觸及時你付全價；之後對同一狀態的每次請求都只是廉價的查表。對費氏數而言，這把約 2^n 的天真遞迴變成 O(n)：相異狀態只有 fib(0)..fib(n) 共 n+1 個，每個以常數工作算一次，其餘都是查表。因此一個記憶化動態規劃的執行時間，是（相異狀態的個數）乘上（為單一狀態組合子結果的成本）。
由於它順著你本來就會寫的遞迴走，記憶化往往是最容易寫對的動態規劃形式：你不必親手推敲一個安全的計算順序——遞迴只在真正需要某子問題時才往下走，所以相依關係會自動解決，而觸及不到的狀態根本不會被計算。不過代價是真實存在的：對大輸入而言，太深的遞迴可能讓呼叫堆疊溢位，每次呼叫都帶有函式呼叫的額外開銷，而當作記憶表的雜湊或陣列也消耗記憶體。當這些代價變得難以承受時，你就把同一條遞迴改成由下而上的製表。
記憶化費氏數：memo = 空映射；fib(n)：若 n <= 1 回傳 n；若 n 在 memo 中回傳 memo[n]；memo[n] = fib(n-1) + fib(n-2)；回傳 memo[n]。每個 fib(k) 的本體只執行一次，所以 fib(50) 只做約 50 次加法，而非數十億次呼叫。
一行快取，就把指數遞迴壓成線性時間。
記憶表的鍵必須涵蓋定義一個子問題的全部資訊——漏掉一個參數會使不同子問題相撞，無聲地汙染答案。也要注意遞迴深度：對非常大的 n，即使工作量是線性，堆疊仍可能溢位。