動態規劃

把算過的答案記下來，不要算第二次。 · ⏱ 約 40 分鐘

你會學到三件事

1. DP 的兩件事：狀態和轉移
2. 為什麼遞迴費氏數會慢到跑不完
3. 邊界值就是「不需要推導的那幾格」

開始之前

費氏數：f(n) = f(n-1) + f(n-2)。

用C++ 入門第 16 課的遞迴寫，f(50) 跑不完。

一、為什麼慢

            f(5)
          /      \
      f(4)        f(3)
     /    \      /    \
  f(3)   f(2)  f(2)  f(1)
  /  \
f(2) f(1)          ← 🔴 f(3) 算了兩次、f(2) 算了三次

同一個東西被重複算了無數次。 f(50) 大約要算 10¹⁰ 次。

而其實只有 51 個不同的答案。

二、記下來

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];
}

從小算到大，每個只算一次。O(n)，f(50) 瞬間。

三、DP 就是兩件事

想 DP 的時候，第一句話永遠是「dp[i] 代表什麼」。

講不清楚 dp[i] 是什麼，後面的轉移一定寫不對—— 而且它會寫出一個「看起來對、樣例也過」的東西。

⚠️ 邊界是「不需要推導的那幾格」。dp[1] 沒有 dp[-1] 可以用， 所以它必須直接給。少給一格，整條鏈就會從錯的地方開始。

四、它和分治的差別

判準：畫出遞迴樹，有沒有同一個節點出現兩次？ 有 → DP。沒有 → 分治。

五、⚠️ 兩個常見的坑

一、溢位（第 1 課）。費氏數第 47 個就超過 int。 DP 的答案常常很大，用 long long。

二、記憶體。dp[10000][10000] 是 10⁸ 個 int ＝ 400 MB，爆掉。

而多半只需要上一列：

// dp[i][j] 只用到 dp[i-1][...] 的話
// 兩列輪流用就夠了 —— 這叫「滾動陣列」

六、常見的幾類

它們的差別全在「dp[i] 是什麼」那一句話上。

完成的樣子

int main() {
    int n = 10;
    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];
    }
    cout << dp[n] << endl;
    return 0;
}

換你了

爬樓梯：一次可以爬 1 階或 2 階，n 階有幾種走法？

⚠️ 先寫出這一句：「dp[i] ＝ ______」。寫不出來就先不要寫程式。

（答案是費氏數。而重點是你自己推出那個轉移，不是那個答案。）

這一課你做了什麼

• 你把一個指數時間的遞迴變成了線性
• 你能說出這一題的狀態、轉移和邊界
• 你知道 DP 和分治的差別在「子問題會不會重疊」

如果卡住了