💡 動態規劃學習指南

← 返回學習中心

什麼是動態規劃？

動態規劃（Dynamic Programming，簡稱 DP）是一種解決最佳化問題的演算法技巧，透過將複雜問題分解為更小的子問題，並儲存子問題的解來避免重複計算。

DP 的核心思想：「記住你已經計算過的東西」

DP 的兩大特性

1. 最佳子結構（Optimal Substructure）

問題的最佳解可以由子問題的最佳解組合而成。

F(n) = F(n-1) + F(n-2)

2. 重疊子問題（Overlapping Subproblems）

在遞迴過程中，子問題會被重複計算多次。

F(5) = F(4) + F(3)
F(4) = F(3) + F(2)...

DP 的兩種實作方式

1. Top-Down（記憶化）

從大問題開始，遞迴解決子問題並儲存結果。

  • 也稱為「記憶化遞迴」
  • 程式碼較直觀
  • 可能有遞迴深度限制

2. Bottom-Up（表格法）

從最小的子問題開始，逐步填表直到解決大問題。

  • 也稱為「迭代 DP」
  • 效能較好（無遞迴開銷）
  • 需要確定填表順序

經典問題：費波那契數列

// 方法1：暴力遞迴 - O(2^n)
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

// 方法2：Top-Down 記憶化 - O(n)
int fibMemo(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
    return memo[n];
}

// 方法3：Bottom-Up 表格法 - O(n)
int fibTab(int n) {
    if (n <= 1) return n;
    vector<int> dp(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];
}

// 方法4：空間優化 - O(n), O(1)
int fibOpt(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1, curr;
    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}

經典問題：0/1 背包問題

// 0/1 背包問題
// weight: 物品重量陣列
// value: 物品價值陣列
// W: 背包容量
// 返回: 最大總價值

int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    
    // 建表
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weight[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w - weight[i-1]] + value[i-1]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

// 空間優化版本 - O(W) 空間
int knapsackOptimized(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<int> dp(W+1, 0);
    
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

常見 DP 問題類型

🚀 前往測驗