Memoization & Tabulation記憶化與表格法

01為什麼需要它

看到這些關鍵字就想到它：重疊子問題、同樣的參數被算很多次、遞迴樹裡有重複的節點、有幾種方法、最少／最多、純函式、@cache、遞迴太深、自頂向下、自底向上。

02核心概念

費氏數列照定義寫成 fib(n) = fib(n−1) + fib(n−2)，遞迴樹會長出大量重複的節點：算 fib(6) 時 fib(2) 被完整算了 5 次。問題不在遞迴本身，而在沒有人記得算過什麼。記憶化（memoization）是自頂向下：保留原本的遞迴，只加一個以參數為 key 的快取，進函式先查、算完先存。表格法（tabulation）是自底向上：不遞迴，先想清楚誰依賴誰，從 base case 開始用迴圈把 dp[0]、dp[1]、dp[2]… 依序填滿。兩者解的是同一組子問題、用同一個轉移式，差別只在順序由誰決定：記憶化讓遞迴按需要自己去問，表格法由你事先排好。

能這樣做有一個前提：函式必須是純函式，回傳值只由參數決定，不依賴全域變數，也不依賴「怎麼走到這裡」。這樣同一組參數第二次被問到時，快取裡的答案一定仍然正確。這組參數就是 DP 的狀態，快取的 key 必須包含所有會影響答案的資訊，少一個就會把不同的問題當成同一個。表格法的正確性則靠填表順序：算 dp[i] 時，它依賴的格子必須都已經填好，也就是按子問題依賴關係的拓撲順序填。對 i 做歸納：base case 正確，每一格只用已經正確的格子算出來，整張表就正確。依賴關係如果有環，兩種寫法都不成立，記憶化會無限遞迴。

複雜度的通用公式是狀態數 × 每個狀態的轉移成本。費氏數列有 n+1 個狀態、每個 O(1)，所以是 O(n)。對照純遞迴：呼叫次數滿足 c(n) = c(n−1) + c(n−2) + 1，解出來是 2·fib(n+1) − 1，大約以 1.618ⁿ 成長，n = 40 就要 3 億 3 千多萬次呼叫；記憶化版只有 2n − 1 次，其中 n+1 次真正計算，其餘都是快取命中。空間上，記憶化要 O(n) 的快取加上 O(n) 深的呼叫堆疊；表格法只要 O(n) 的陣列，而且 dp[i] 只用到前兩格，可以改成兩個變數滾動，降到 O(1)。

怎麼選：記憶化最好寫，暴力遞迴加三行就好，而且只會算到真正走得到的狀態，狀態範圍極大但實際走到的很少時只能用它；代價是遞迴深度，Python 預設上限 1000 層，fib_memo(5000) 會直接 RecursionError。表格法沒有遞迴、常數小、方便做空間壓縮，但要自己想清楚填表順序，而且每個狀態都會算到。常見的坑：Python 把 memo= 寫成預設參數，換一組輸入仍讀到上一組的答案；@cache 的參數必須可雜湊，串列要改成 tuple 或改用索引當狀態；C++ 的 long long 到 fib(93) 就溢位。和相鄰課程的差別：分治的子問題不重疊（合併排序的左右兩半沒有交集），加快取沒有幫助；回溯要列出每一條路徑，若只問「有幾種」「最好是多少」，而且之後怎麼走只取決於目前狀態，就能改寫成記憶化。下一課的一維 DP 會把表格法加空間壓縮當成預設寫法。

03演算法步驟

1. 1先寫出暴力遞迴，把函式的意義說清楚：ways(i) 回傳「走到第 i 階有幾種走法」。參數就是狀態，base case 寫在最前面。
2. 2確認兩件事：遞迴樹裡同一組參數出現不只一次（重疊子問題），而且回傳值只由參數決定。不依賴全域變數或走過的路徑，才能快取。
3. 3記憶化：開一個以狀態為 key 的 dict 或陣列（沒算過標成 −1）。進函式先查，有就回傳；沒有就照原本的遞迴算，存進快取再回傳。Python 可以直接加 @cache。
4. 4表格法：把函式換成陣列 dp，先填 base case，再用迴圈照「被依賴的先算」的順序填，每一格套同一個轉移式。dp[i] 依賴比 i 小的格子，就讓 i 由小到大。
5. 5空間壓縮：看轉移式只用到哪幾格。只用到前 k 格就改成 k 個變數滾動，空間從 O(n) 降到 O(1)。
6. 6估算狀態數 × 轉移成本確認在時限內。遞迴深度可能上萬時改用表格法；狀態範圍很大但實際走到的很少時，留在記憶化。

04互動示範

計算 fib(6)，畫面上的樹用 f(n) 代表 fib(n)。整棵遞迴樹一開始是淡色，按「下一步」依呼叫順序點亮，藍色是正在進行的那次呼叫，灰底是第一次碰到的 base case。「純遞迴」模式共 25 次呼叫，黃色是重算已經算過的子問題，佔了 18 次，連整棵 f(4)、f(3) 子樹都被重新展開。切到「記憶化」，同一個問題只剩 11 次呼叫，綠色是快取命中，底下的子樹不再展開。樹下方的卡片統計兩種模式的呼叫次數，旁邊的小表列出 n = 6、10、20、30 時的差距，到 n = 30 已經是 2,692,537 次對 59 次。

05程式碼

同一個 fib 寫成四個版本：純遞迴、記憶化（手寫快取與 @cache）、表格法、兩個變數的空間壓縮版，方便對照每一步改了什麼；C++ 的快取用陣列，以 −1 代表還沒算過。再用「每次可以選不同步數的爬樓梯」示範同一套轉換套在有多個選擇的轉移式上，Python 的記憶化版刻意把 @cache 放在函式裡，避免不同的 steps 共用快取。

from functools import cache


# 1. 純遞迴：照定義寫，呼叫次數約 1.618ⁿ，n = 40 就要三億多次
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


# 2. 記憶化（自頂向下）：原本的遞迴 + 以參數為 key 的快取
def fib_memo(n, memo=None):
    if memo is None:                       # 別寫 memo={}：預設值只建立一次，會被所有呼叫共用
        memo = {}
    if n in memo:                          # 先查快取
        return memo[n]
    if n <= 1:
        result = n                         # base case
    else:
        result = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    memo[n] = result                       # 算完先存再回傳
    return result


@cache                                     # 標準庫幫你做同一件事：參數就是快取的 key
def fib_cached(n):
    return n if n <= 1 else fib_cached(n - 1) + fib_cached(n - 2)


# 3. 表格法（自底向上）：不遞迴，從 base case 往上填
def fib_table(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):              # 算 dp[i] 時，dp[i-1] 和 dp[i-2] 一定已經填好
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


# 4. 空間壓縮：dp[i] 只用到前兩格，留兩個變數就夠，O(1) 空間
def fib_rolling(n):
    a, b = 0, 1                            # a = fib(i)，b = fib(i+1)
    for _ in range(n):
        a, b = b, a + b
    return a


# 推廣：爬 n 階，每次可以走 steps 裡任一種步數，有幾種走法（steps = [1, 2] 就是 LeetCode 70）
def climb_memo(n, steps):
    @cache                                 # 快取定義在函式裡：每次呼叫 climb_memo 都是新的一份
    def ways(i):                           # 狀態只有 i；steps 在這次呼叫中不變，不必放進 key
        if i == 0:
            return 1                       # 已經站在第 0 階：一種走法（什麼都不做）
        return sum(ways(i - s) for s in steps if s <= i)
    return ways(n)


def climb_table(n, steps):
    dp = [1] + [0] * n                     # dp[i] = 走到第 i 階的走法數
    for i in range(1, n + 1):
        dp[i] = sum(dp[i - s] for s in steps if s <= i)
    return dp[n]


if __name__ == "__main__":
    print(fib_naive(20), fib_memo(20), fib_cached(20))    # 6765 6765 6765
    print(fib_table(90), fib_rolling(90))                 # 2880067194370816120 2880067194370816120
    print(climb_memo(10, [1, 2]), climb_table(10, [1, 2]))          # 89 89
    print(climb_memo(10, [1, 3, 5]), climb_table(10, [1, 3, 5]))    # 47 47
    print(len(str(fib_table(5000))))                      # 1045（fib(5000) 有 1045 位數）
    # fib_memo(5000) 則會 RecursionError：遞迴深度超過 Python 預設上限 1000

06練習題

• LeetCode 509Fibonacci Number（記憶化、表格法、滾動變數各寫一次）Easy
• LeetCode 70Climbing Stairs（從暴力遞迴改成表格法）Easy
• LeetCode 1137N-th Tribonacci Number（滾動三個變數）Easy
• LeetCode 377Combination Sum IV（程式碼裡的爬樓梯推廣）Medium
• LeetCode 2140Solving Questions With Brainpower（從後往前填表）Medium
• LeetCode 1553Minimum Number of Days to Eat N Oranges（n 到 2×10⁹，只能記憶化）Hard