動態規劃

🎯 什麼情境該想到我

當你「寫出暴力遞迴，發現同一個子問題被算了很多次」的時候。
★ DP 的難處從來不是「怎麼寫」，是「狀態怎麼定義」。 這頁的重點放在狀態設計與判準。

⚙️ 怎麼用（兩個前提與設計流程）

★ 兩個必要條件（缺一不可）

條件	意思	沒有它會怎樣
① 最佳子結構	最佳解包含子問題的最佳解	子問題算對了也拼不出正確答案
② 重疊子問題	同一個子問題被重複遇到	沒有重複就不需要記憶化 → 用分治法就好

費氏數列的遞迴樹（純分治）：
  fib(5)
  ├─ fib(4) ─┬─ fib(3) ─┬─ fib(2) ⋯
  │          └─ fib(2)  ★ 重複
  └─ fib(3) ─┬─ fib(2)  ★ 重複
             └─ fib(1)
→ O(φⁿ) 指數爆炸，但不同的子問題只有 n 個
→ ★ 加記憶化立刻變 O(n)

★ 判準：畫出遞迴樹，看有沒有重複節點。
有重複 → DP；沒重複 → 分治法；每步局部最佳就全域最佳 → 貪婪演算法。

兩種實作方式

	自頂向下（記憶化）	自底向上（表格）
寫法	遞迴 + cache	迴圈填表
優點	貼近原始遞迴，好寫好想；只算用得到的狀態	無遞迴開銷；★ 可做空間優化
缺點	遞迴堆疊、函式呼叫開銷	要想清楚填表順序
建議	★ 先寫記憶化把答案做對，再視需要轉表格

// 自頂向下：先讓它「對」
func fib(n int, memo map[int]int) int {
    if n < 2 { return n }
    if v, ok := memo[n]; ok { return v }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}
 
// 自底向上 + ★ 滾動變數（空間 O(n) → O(1)）
func fibFast(n int) int {
    a, b := 0, 1
    for i := 0; i < n; i++ { a, b = b, a+b }
    return a
}

★ 設計流程（真正的難點在第 1 步）

1. ★ 定義狀態     dp[i] / dp[i][j] 「到底代表什麼」—— 要能用一句話說清楚
2. 寫出轉移方程   dp[i] 怎麼從更小的狀態算出來
3. 決定邊界條件   最小的狀態是什麼
4. 決定填表順序   確保用到的狀態都已算好
5. 找出答案在哪   不一定是 dp[n]，可能是 max(dp[*])
6. 空間優化       通常可以把二維壓成一維

★ 狀態定義的三個常見錯誤：

定義模糊 —— 「dp[i] 是前 i 個的最佳解」到底含不含第 i 個？含與不含是兩種不同的 DP。
維度不夠 —— 轉移時發現「還需要另一個資訊」→ 就是維度漏了（例如背包要加「剩餘容量」）
狀態不獨立 —— 轉移依賴的東西不只在狀態裡，正確性就沒了

五個經典題型（辨識出型別就解掉一半）

型別	狀態	代表題
線性 DP	`dp[i]` = 到第 i 個為止	最大子陣列、打家劫舍、LIS
背包	`dp[i][w]` = 前 i 個物品、容量 w	0-1 背包、完全背包、硬幣找零
雙序列	`dp[i][j]` = A 前 i 個 vs B 前 j 個	LCS、編輯距離、正則匹配
區間 DP	`dp[i][j]` = 區間 [i,j]	矩陣鏈乘、戳氣球、回文分割
狀態壓縮	`dp[mask]` = 位元集合	TSP、集合覆蓋（n ≤ 20）

編輯距離（Levenshtein） —— 最值得記住的一個，因為它到處都在用（拼寫檢查、diff、模糊比對）：

func editDistance(a, b string) int {
    m, n := len(a), len(b)
    dp := make([]int, n+1)               // ★ 滾動一維
    for j := 0; j <= n; j++ { dp[j] = j }
    for i := 1; i <= m; i++ {
        prev := dp[0]                    // ★ dp[i-1][j-1]，被覆蓋前先存起來
        dp[0] = i
        for j := 1; j <= n; j++ {
            tmp := dp[j]
            if a[i-1] == b[j-1] {
                dp[j] = prev             // 不用動
            } else {
                dp[j] = 1 + min(prev,    // 取代
                                dp[j],   // 刪除（上方）
                                dp[j-1]) // 插入（左方）
            }
            prev = tmp
        }
    }
    return dp[n]
}

★ 滾動陣列的關鍵是「被覆蓋之前先把 dp[i-1][j-1] 存起來」——這是一維壓縮最容易寫錯的一行。

空間優化的通則

dp[i] 只依賴 dp[i-1] → 兩個變數就夠
dp[i][j] 只依賴上一列 → 一維滾動
0-1 背包一維時容量要倒著遍歷（避免同一個物品被用兩次）；完全背包要正著
★ 這個方向差異是背包題最經典的坑

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 沒有最佳子結構就不能用。典型反例：有負權時的最長路徑——子路徑的最長不構成整體的最長。
狀態空間會爆炸。dp[i][j][k][mask] 很快就超出記憶體。狀態超過約 $1 0^{8}$ 個就該重新設計，或改用啟發式／近似演算法。
★ 能用貪婪演算法就別用 DP。貪婪通常是 $O (n lo g n)$ 且省空間。但貪婪要能證明（見該頁的交換論證）。
記憶化的 map 有開銷。狀態是連續整數時用陣列（[]int）而非 map[int]int，實測差距可以到數倍。
要輸出「方案」而不只是「最佳值」時，要額外記錄決策來源（parent 陣列）再回溯。
DP 不等於「會 DP」。真正的能力是辨識題型 + 定義狀態，不是背轉移方程。
實務上 DP 出現在：diff 工具、拼寫檢查、生物序列比對、資源排程、工具-資料驅動的模板推導這類字串比對場景——不只是刷題用的。

🔗 相關工具

分治法 —— 子問題不重疊時用它；以及兩者的界線
貪婪演算法 —— 更強的條件、更快的解法
Floyd-Warshall 全對最短路 —— 一個純粹的 DP（在圖上）
Bellman-Ford 最短路徑 —— 也是 DP（逐輪放寬邊數上限）
工具-演算法設計策略、工具-時間複雜度分析 —— 決策層
演算法導論

Quartz 5

Explorer