動態規劃

把算過的答案記下來，不要算第二次。 · ⏱ 約 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 個不同的答案。

二、記下來

算過的就記起來，不要再算第二次：

1vector<int> dp(n + 1);2dp[0] = 0;3dp[1] = 1;4for (int i = 2; i <= n; i++) {5    dp[i] = dp[i - 1] + dp[i - 2];6}

從小算到大，每個只算一次。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，爆掉。

而多半只需要上一列：

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

六、常見的幾類

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

完成的樣子

1#include <iostream>2#include <vector>3using namespace std;4int main() {5    int n = 10;6    vector<int> dp(n + 1);7    dp[0] = 0;8    dp[1] = 1;9    for (int i = 2; i <= n; i++) {10        dp[i] = dp[i - 1] + dp[i - 2];11    }12    cout << dp[n] << endl;13    return 0;14}

換你了

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

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

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

到編輯器做這一題：練習：爬樓梯——n 階有幾種走法

做一個

-2 1 -3 4 -1 2 1 -5 4，找出連續一段加起來最大是多少。

🔴 狀態是「以第 i 格結尾的最大和」，而轉移只有一個選擇： 接上前面那一段，還是從這裡重新開始。 ⚠️ 試遍所有起點終點是 O(n²)，而這個做法是一趟。

到編輯器做這一題：做一個：最大連續子陣列和

這一課你做了什麼

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

如果卡住了