[algorithms] Dynamic Programming 動態規劃

視覺化概覽

graph TD
    F5["fib(5)"] --> F4["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4 --> F3b["fib(3) ⚡重複"]
    F4 --> F2a["fib(2)"]
    F3a --> F2b["fib(2) ⚡重複"]
    F3a --> F1a["fib(1)=1"]
    F3b -.->|"查表取得"| memo["備忘錄 Memo\n避免重複計算"]
    F2b -.->|"查表取得"| memo

    style memo fill:#4CAF50,color:#fff
    style F3b fill:#FF9800,color:#fff
    style F2b fill:#FF9800,color:#fff

你每天都在用動態規劃

你用過 git diff 嗎？它怎麼算出兩個檔案的差異？LCS（最長共同子序列）。你打過字嗎？手機鍵盤的自動校正怎麼知道你想打什麼？Edit Distance（編輯距離）。你看過 Google Docs 的自動換行嗎？Text Wrapping DP。

工程場景	對應 DP 問題
git diff / diff 工具	LCS（最長共同子序列）
手機鍵盤自動校正、拼字檢查	Edit Distance（編輯距離）
文字編輯器的自動換行	Text Wrapping DP
Webpack code splitting	背包問題（chunk 大小最佳化）
資料庫 query optimizer	矩陣鏈乘積（join 順序最佳化）
音訊/影片壓縮（MPEG）	最長遞增子序列的變體
股票交易策略回測	買賣股票問題

什麼是動態規劃？

用「記住」來避免「重複計算」。

把大問題拆成小問題，記住小問題的答案，用來解決大問題。

遞迴（重複計算）:
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)  ← fib(3) 算了兩次！
fib(3) = fib(2) + fib(1)  ← fib(2) 算了更多次！

DP（記住結果）:
fib(0) = 0  → 記住
fib(1) = 1  → 記住
fib(2) = fib(1) + fib(0) = 1  → 記住
fib(3) = fib(2) + fib(1) = 2  → 記住
fib(4) = fib(3) + fib(2) = 3  → 記住
fib(5) = fib(4) + fib(3) = 5  ✓

DP 的兩種做法

1. Top-Down（記憶化遞迴）

從大問題往下拆，遇到算過的直接取答案。

int[] memo = new int[n + 1];
 
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];  // 已經算過
    memo[n] = fib(n-1) + fib(n-2);     // 記住結果
    return memo[n];
}

2. Bottom-Up（表格法）

從小問題往上算，填表格。

int fib(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // 查表
    }
    return dp[n];
}

DP 的思考框架：從暴力到最佳解

很多人覺得 DP 很難，是因為直接跳到「狀態轉移式」。其實 DP 有一套固定的思考流程：

Step 1：先寫暴力遞迴

不要想最佳化，先用最笨的方法解題。這一步最重要。

// 例：硬幣找零 — 用最少硬幣組成 amount
function coinChange(coins: number[], amount: number): number {
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
 
  let min = Infinity;
  for (const coin of coins) {
    const result = coinChange(coins, amount - coin);
    min = Math.min(min, result + 1);
  }
  return min;
}

Step 2：畫遞迴樹，找重疊子問題

coinChange([1,2,5], 6)
├── coinChange(5)      ← amount-1
│   ├── coinChange(4)
│   │   ├── coinChange(3)  ← 這裡重複了！
│   │   └── ...
│   └── coinChange(3)     ← 這裡也有！
├── coinChange(4)      ← amount-2，跟上面重複！
└── coinChange(1)      ← amount-5

看到 coinChange(3) 和 coinChange(4) 被算了好幾次 → 有重疊子問題 → 能用 DP。

Step 3：加 memo（Top-Down）

把遞迴結果存起來，重複呼叫時直接取。

function coinChange(coins: number[], amount: number): number {
  const memo = new Map<number, number>();
 
  function dp(remaining: number): number {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    if (memo.has(remaining)) return memo.get(remaining)!; // 查表
 
    let min = Infinity;
    for (const coin of coins) {
      min = Math.min(min, dp(remaining - coin) + 1);
    }
    memo.set(remaining, min); // 存表
    return min;
  }
 
  const result = dp(amount);
  return result === Infinity ? -1 : result;
}

Step 4：轉成 Bottom-Up（可選）

從小問題往上填表，通常空間效率更好。

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
 
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
 
// coinChange([1, 2, 5], 11) → 3（5+5+1）

關鍵心法：暴力遞迴 → 畫樹找重複 → 加 memo → 轉 bottom-up。這四步在任何 DP 問題都適用。

---

經典 DP 問題

1. 費波那契數列

問題：求第 n 個費波那契數

狀態轉移：dp[i] = dp[i-1] + dp[i-2]

dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 3
dp[5] = 5
...

2. 爬樓梯

問題：每次可以爬 1 或 2 階，有幾種方法到第 n 階？

狀態轉移：dp[i] = dp[i-1] + dp[i-2]（跟費波那契一樣！）

到第 1 階：1 種 (1)
到第 2 階：2 種 (1+1, 2)
到第 3 階：3 種 (1+1+1, 1+2, 2+1)
到第 4 階：5 種
...

3. 最長共同子序列 (LCS)

問題：找兩個字串的最長共同子序列

範例：ABCDE 和 ACE → LCS = ACE，長度 3

狀態轉移：

如果 s1[i] == s2[j]:
    dp[i][j] = dp[i-1][j-1] + 1
否則:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

填表範例（s1 = “ACE”, s2 = “ABCDE”）：

      ""  A  B  C  D  E
  ""   0  0  0  0  0  0
   A   0  1  1  1  1  1
   C   0  1  1  2  2  2
   E   0  1  1  2  2  3

工程場景：git diff 的原理

git diff 要顯示兩個檔案版本的差異。它的核心就是 LCS：先找出兩版本的「共同部分」（不用改的行），剩下的就是新增（+）和刪除（-）的行。

// 簡化版 diff：用 LCS 找出兩段文字的差異
function simpleDiff(oldLines: string[], newLines: string[]): string[] {
  // 先算 LCS 表格
  const m = oldLines.length, n = newLines.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
 
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (oldLines[i - 1] === newLines[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
 
  // 回溯產生 diff 輸出
  const result: string[] = [];
  let i = m, j = n;
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && oldLines[i - 1] === newLines[j - 1]) {
      result.unshift(`  ${oldLines[i - 1]}`);
      i--; j--;
    } else if (j > 0 && (i === 0 || dp[i][j - 1] >= dp[i - 1][j])) {
      result.unshift(`+ ${newLines[j - 1]}`);
      j--;
    } else {
      result.unshift(`- ${oldLines[i - 1]}`);
      i--;
    }
  }
  return result;
}
 
const oldCode = ['const x = 1;', 'const y = 2;', 'console.log(x);'];
const newCode = ['const x = 1;', 'const z = 3;', 'console.log(x);', 'console.log(z);'];
console.log(simpleDiff(oldCode, newCode).join('\n'));
// Output:
//   const x = 1;
// - const y = 2;
// + const z = 3;
//   console.log(x);
// + console.log(z);

4. 0/1 背包問題

問題：物品有重量和價值，背包有容量限制，求最大價值

範例：

物品: [(重量=2, 價值=3), (重量=3, 價值=4), (重量=4, 價值=5)]
背包容量: 5
最佳選擇: 物品1 + 物品2 = 價值 7

狀態轉移：

dp[i][w] = max(
    dp[i-1][w],                         // 不選第 i 個
    dp[i-1][w-weight[i]] + value[i]     // 選第 i 個
)

5. 硬幣找零

問題：用最少的硬幣組成目標金額

範例：硬幣 [1, 2, 5]，金額 11 → 最少 3 枚 (5+5+1)

狀態轉移：dp[i] = min(dp[i], dp[i - coin] + 1)

dp[0] = 0
dp[1] = dp[0] + 1 = 1  (用 1)
dp[2] = dp[0] + 1 = 1  (用 2)
dp[3] = dp[1] + 1 = 2  (1+2)
dp[4] = dp[2] + 1 = 2  (2+2)
dp[5] = dp[0] + 1 = 1  (用 5)
...

6. 最長遞增子序列 (LIS)

問題：找陣列中最長的遞增子序列

範例：[10, 9, 2, 5, 3, 7, 101] → LIS = [2, 3, 7, 101]，長度 4

狀態轉移：

對於每個 i:
    dp[i] = max(dp[j] + 1)  其中 j < i 且 nums[j] < nums[i]

如何判斷是 DP 問題？

1. 最佳解問題：求最大、最小、最長、最短
2. 計數問題：有幾種方法、幾種組合
3. 可行性問題：能不能達成某目標
4. 有重疊子問題：小問題會被重複計算

DP 解題步驟

1. 定義狀態：dp[i] 代表什麼？
2. 找狀態轉移：dp[i] 和 dp[i-1] 的關係是什麼？
3. 定義初始值：dp[0] 是多少？
4. 確定計算順序：從小到大還是從大到小？

時間複雜度

問題	遞迴	DP
費波那契	O(2^n)	O(n)
LCS	O(2^(m+n))	O(m×n)
背包	O(2^n)	O(n×W)
硬幣找零	指數級	O(n×amount)
LIS	O(2^n)	O(n²)

空間優化技巧

如果 dp[i] 只依賴 dp[i-1]，可以只用兩個變數：

// 原本 O(n) 空間
int[] dp = new int[n];
 
// 優化成 O(1) 空間
int prev = 0, curr = 1;
for (...) {
    int next = prev + curr;
    prev = curr;
    curr = next;
}

什麼時候不需要 DP

• 沒有重疊子問題：每個子問題只算一次（例如 merge sort）→ 用 分治法
• 有貪心性質：每步的最佳選擇就是全域最佳（例如活動選擇）→ 用 貪心演算法
• 狀態空間太大：DP 表格放不下記憶體（例如圍棋）→ 用近似演算法或啟發式搜尋

---

延伸閱讀

• 圖演算法 — Floyd-Warshall 是 DP 在圖上的經典應用
• 貪心演算法 — DP 的簡化版，不需要回溯
• 分治法 — 子問題不重疊時用分治而非 DP
• Hash Table — Memoization 的底層用 hash map 儲存

相關檔案

• Java 實作：DynamicProgramming.java
• 視覺化：dynamic-programming.html