Dynamic Programming
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];
}
這段程式碼透過儲存前兩項的答案來避免重複計算，以加快求解費波那契數列的速度。
DP 解題步驟
- 定義狀態：
dp[i]代表什麼？ - 狀態轉移方程：
dp[i]和dp[i-1]、dp[i-2]... 的關係 - Base Case：起始條件是什麼？
- 遍歷順序：由小到大（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];
}
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];
}
Top-Down vs Bottom-Up
| 方法 | 優點 | 缺點 |
|---|---|---|
| Top-Down（記憶化遞迴） | 直覺、只算需要的子問題 | 遞迴深度限制、呼叫堆疊開銷 |
| Bottom-Up（迭代） | 無遞迴開銷、可空間優化 | 需要確定遍歷順序 |