動態規劃教學：原理、程式碼與範例

動態規劃解決什麼問題

許多問題問的是最好、最便宜或方法數：湊出某個金額最少需要幾枚硬幣、兩個字串的最長共同子序列、背包裝得下的最有價值物品組合、穿過網格的路徑數量。直接的遞迴解法往往會以指數次數重複計算相同的小案例，DP 則消除了這些重複。

這個名稱來自 Richard Bellman，他在 1950 年代發展出這套方法。這裡的「programming」指的是規劃或填寫表格，而不是寫程式。

用白話說明原理

單純的遞迴費氏數列就能看出問題。fib(5) 會呼叫 fib(4) 和 fib(3)，而 fib(4) 又會再呼叫一次 fib(3)，依此類推：呼叫次數呈指數成長。只要第一次算出結果時就儲存起來，之後的每次呼叫都能立即得到答案。

1. 定義狀態：子問題長什麼樣子？例如 best[a] = 湊出金額 a 所需的最少硬幣數。
2. 寫出遞迴關係式：如何由較小的狀態算出某個狀態？best[a] = 1 + min(best[a - c] for each coin c)。
3. 設定基底情況：best[0] = 0。
4. 選擇順序：由上而下搭配記憶化，或由下而上，確保較小的狀態一定先被填好。
5. 從正確的狀態讀出答案，必要時再重建實際的選擇。

由上而下：用 functools 做記憶化

在 Python 中，functools.cache（Python 3.9+）或 functools.lru_cache 只要一行就能為函式加上記憶化：

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))  # 23416728348467685

如果沒有這個裝飾器，fib(80) 會進行超過 10¹⁶ 次遞迴呼叫。加上之後，0 到 80 的每個值都只計算一次。

範例：由下而上的硬幣找零

硬幣面額為 1、3、4，金額為 6。貪婪做法會先拿 4，需要 4 + 1 + 1 = 3 枚硬幣，但 3 + 3 只要 2 枚。DP 會對 a = 0 到 6 填寫 best[a]，找出真正的最小值：

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

print(min_coins([1, 3, 4], 6))  # 2
print(min_coins([2], 3))        # -1

二維範例：最長共同子序列

許多處理兩個序列的 DP 問題都使用網格：dp[i][j] 是其中一個字串的前 i 個字元與另一個字串的前 j 個字元的答案。以最長共同子序列（LCS）為例，如果字元相符，就沿對角線延伸；否則，在捨棄任一字串的一個字元之間取較佳者。

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))  # 4

長度為 4 的 LCS 之一是 BCBA。同樣的表格結構也能解編輯距離，文字比對（diff）工具就是用它來衡量兩個字串的差異程度。

時間與空間複雜度

通則：時間 = 狀態數 × 每個狀態的運算量；空間 = 儲存的狀態數。

背包問題的 O(n × W) 是偽多項式：它取決於數值 W，而不是輸入的位元大小，所以當 W 很大時會很慢。

常見錯誤與何時使用 DP

• 狀態定義錯誤：如果遞迴關係式需要狀態沒有記錄的資訊（例如哪些物品已被使用），答案就會出錯。請把該資訊加進狀態中。
• 填表順序錯誤：由下而上的迴圈必須在讀取每個狀態之前先算好它。
• 表格大小差一：長度為 n 的字串需要 n + 1 列，才能包含空前綴。
• 遞迴太深：對 10,000 個狀態做記憶化遞迴可能超過 Python 的遞迴深度限制；請改成由下而上。
• 不可雜湊的參數：functools.cache 需要可雜湊的參數，所以請傳入 tuple 而不是 list。

典型的面試題與實際應用：爬樓梯、打家劫舍、最長遞增子序列、單字拆分、網格中的不同路徑、編輯距離、背包問題、矩陣鏈乘法；實務上則有生物資訊學的序列比對、diff 工具、拼字檢查、語音辨識（Viterbi 演算法），以及 Bellman-Ford 等最短路徑演算法。