動態規劃：智慧的長者

演算法背後的故事：命運的階梯

想像妳站在一段有 10 級台階的樓梯底部。妳每次可以跨 1 級或 2 級台階。到達頂層有多少種走法？

• 要到達第 10 級，妳一定是由第 9 級（跨 1 步）或者第 8 級（跨 2 步）跳上來的。
• 所以，走法(10) = 走法(9) + 走法(8)。
• 但是要找到 走法(9)，妳需要 走法(8) 和 走法(7)。

發現了嗎？妳需要 走法(8) 兩次！在普通的遞迴方法中，妳會一遍又一遍地重新計算 走法(8)。對於 100 級的樓梯，妳會重複計算數十億次。

動態規劃 (Dynamic Programming) 像長者一樣告誡妳：「停下！第一次算出第 8 級的答案時，將她寫下來。下次需要時，直接翻筆記本。」

這就是 DP 的精髓：遞推關係 + 備忘錄。

為什麼需要它？

• 金融建模： 計算投資組合的最大回報。
• 路徑規劃： Google 地圖在複雜的城市中尋找最短路徑。
• 資源分配： 背包問題——在有限的空間內裝入價值最高的物品。
• 生物資訊學： 比對 DNA 序列。

演算法是如何「思考」的

該演算法有兩種工作方式：

1. 自頂向下 (備忘錄)： 從大問題開始（第 10 級）。如果妳遇到一個子問題，先查筆記本。如果它是空的，計算並保存。
2. 自底向上 (填表)： 從最小的問題開始（第 1 級）。一步步填表，直到達到目標。

DP 的三大支柱：

1. 最優子結構： 大問題的最優解由小問題的最優解構建而成。
2. 重疊子問題： 妳會不斷遇到相同的微小疑問。
3. 狀態轉移方程： 一個清晰的公式（如 $F(n) = F(n-1) + F(n-2)$）。

工程決策：時空權衡

DP 是終極的「以空間換時間」。

• 時間： 從 $O(2^N)$（指數級/永遠算不完）降低到 $O(N^2)$ 或 $O(N)$（線性/瞬間完成）。
• 空間： 妳需要 $O(N)$ 的記憶體來儲存筆記本。
• 優化： 通常妳只需要「最後兩個結果」就能推導出下一個，這允許妳將空間優化到 $O(1)$。

實作參考 (Python)

# 0/1 背包問題：在重量限制下獲得最大價值
def knapsack(weights, values, capacity):
    n = len(values)
    # 1. 創建筆記本 (表格)
    # dp[i][w] = 使用前 i 個物品、重量限制為 w 時的最大價值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # 2. 從過去構建未來 (自底向上)
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                # 抉擇：拿還是不拿
                dp[i][w] = max(
                    values[i-1] + dp[i-1][w - weights[i-1]], # 拿
                    dp[i-1][w]                               # 不拿
                )
            else:
                # 太重了，只能放棄
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

# 使用範例
vals = [60, 100, 120]
wts = [10, 20, 30]
cap = 50
print(f"最大價值: {knapsack(wts, vals, cap)}")

小結

動態規劃教會我們：記憶就是力量。透過拒絕重複過去的錯誤（或工作），我們獲得了解決看似不可能的大規模問題的能力。它提醒我們，在工程中，最優雅的解決方案往往只是一個記錄了我們所有已知知識的、井然有序的筆記本。