7.2 動態規劃作為迭代#

概念說明#

動態規劃（DP）常被當成獨立主題，但用本書的語言看，它就是離散世界的不動點迭代。DP 的靈魂是遞迴方程：

\[ \text{dp}[i] = F(\text{dp}[i_1], \text{dp}[i_2], \dots), \qquad \text{dp}[\text{base}] = \text{已知} \]

這定義了一個把「表」映到自身的轉換 \(G\) ，而正確的 DP 表正是 \(G\) 的不動點。求這個不動點有兩種迭代順序：

自上而下（遞迴＋備忘錄）：從問題出發，遇到子問題先查表、沒有就遞迴。它就是 1.3 節說的「把重複計算砍掉的遞迴」。
自下而上（填表）：按依賴順序（通常是下標遞增）迭代填表。等價於對依賴 DAG 做拓撲排序後逐節點計算。

兩者計算同一個不動點，時間複雜度相同；差別在遞迴有堆疊開銷與深度限制，填表有快取友善與可省空間（滾動陣列）的優勢。

正確性論證正是 1.2 節不變式的翻版：歸納不變式——「填完第 \(i\) 項時，dp[0..i] 皆為對應子問題的最優值」。基底是 base case，維持性由遞迴方程＋子問題最優性（最優子結構）保證，終止性由下標嚴格遞減/遞增（良序量度）保證。

複雜度分析有簡單口訣：狀態數 × 每狀態轉移成本。費波那契： \(n\) 個狀態 × \(O(1)\) 轉移 = \(O(n)\) ，對比樸素遞迴的 \(O(\varphi^n)\) ——差距完全來自「不重複算同一狀態」。背包： \(nW\) 個狀態 × \(O(1)\) = \(O(nW)\) 。最長共同子序列（LCS）： \(mn\) 狀態 × \(O(1)\) 。

DP 也與 4.3 節相通：對依賴是環的情況（如最短路徑允許任意順序鬆弛），填表順序不存在，需改用 Bellman-Ford 式的「反覆鬆弛直到不動」——正是資料流分析（7.3 節）的套路。

生活類比#

爬樓梯只許一步或兩步，問有幾種走法。與其把每條路都走一遍（指數爆炸），不如記住「到第 \(k\) 階的方法數」，往上遞推——像記帳：今天餘額只由昨天的進出決定，不必重演全部歷史。

演算法步驟#

設計 DP 的五步（自下而上）：

定義狀態：dp[i] 的精確意義（最易出錯處）。
寫出轉移方程與 base case。
確定計算順序（依賴關係無環）。
實作填表；檢查能否滾動陣列省空間。
用不變式論證正確性，用小案例驗證。

Python 範例#

三個經典：爬樓梯（遞迴 vs 迭代）、0/1 背包、LCS。

# 1) 費波那契：兩種迭代
def fib_memo(n, memo={}):
    if n <= 1: return n
    if n not in memo: memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

def fib_table(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# 2) 0/1 背包（一維滾動陣列）
def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for cap in range(W, w - 1, -1):   # 倒序防止重複選取
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[W]

# 3) 最長共同子序列
def lcs(s, t):
    m, n = len(s), len(t)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        cur = [0] * (n + 1)
        for j in range(1, n + 1):
            cur[j] = prev[j-1] + 1 if s[i-1] == t[j-1] else max(prev[j], cur[j-1])
        prev = cur
    return prev[n]

print(fib_memo(30), fib_table(30))
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))   # 10
print(lcs("ABCBDAB", "BDCABA"))                  # 4 (BCBA/BCAB)

複雜度與收斂性分析#

時間 = 狀態數 × 轉移成本，空間 = 狀態數（可再壓縮）。爬樓梯空間壓到 \(O(1)\) ；背包 \(O(W)\) ；LCS 每列 \(O(\min(m,n))\) 。與遞迴對比：費波那契樸素遞迴 \(O(\varphi^n) \approx O(1.618^n)\) ，迭代 \(O(n)\) ——重複子問題越多，DP 獲利越大；若子問題互不重疊（如二分搜尋、合併排序），分治即可、不需 DP。反例警示：硬套 DP 於有後效性的問題（狀態依賴未來）會得到循環定義，此時應改建模或用 Bellman-Ford 式鬆弛迭代。

練習#

把爬樓梯問題加上「禁止連續兩步」的規則，設計新狀態與轉移，並寫不變式論證。
實作零錢兌換（最少枚數，幣值無限供應），分析為何內外層迴圈順序決定「組合數」還是「排列數」。
用「狀態數 × 轉移成本」推導最長遞增子序列（ \(O(n^2)\) 版）與其 \(O(n \log n)\) 貪心＋二分版的差異。