跳到主要內容
← 回到學習

學習 · 面試考題

Dynamic Programming

By Kurau2 分鐘閱讀

目錄 · 3 個段落
  1. 01DP 解題步驟
  2. 02經典題型
  3. 03Top-Down vs Bottom-Up

Dynamic Programming動態規劃是一種解決問題的方法，專門用於解決求最值的問題。通過計算部分子問題的答案，並將這些答案存儲在數組或哈希表中，我們可以避免重复計算以提高效率。

舉個例子，假設我們想要求斐波那契數列的第n項，這是一個很好的應用動態規劃的問題。我們可以用以下代碼來實現：

function fibonacci(n) {
  let dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
javascript

這段程式碼透過儲存前兩項的答案來避免重複計算，以加快求解費波那契數列的速度。

DP 解題步驟

  1. 定義狀態：dp[i] 代表什麼？
  2. 狀態轉移方程：dp[i] 和 dp[i-1]、dp[i-2]... 的關係
  3. Base Case：起始條件是什麼？
  4. 遍歷順序：由小到大（Bottom-Up）或由大到小（Top-Down + Memoization）

經典題型

爬樓梯（Climbing Stairs）

function climbStairs(n) {
  if (n <= 2) return n;
  let dp = [0, 1, 2];
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
javascript

0/1 背包問題

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(capacity + 1).fill(0);
  for (let i = 0; i < n; i++) {
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}
javascript

Top-Down vs Bottom-Up

方法優點缺點
Top-Down（記憶化遞迴）直覺、只算需要的子問題遞迴深度限制、呼叫堆疊開銷
Bottom-Up（迭代）無遞迴開銷、可空間優化需要確定遍歷順序

目錄