# 經典動態規劃問題 Classic DP Problems
[前一篇](https://hackmd.io/@ShanC/Intro-to-DP)已經講過什麼是 DP，這篇來介紹幾種入門的題型
## 一些遞迴式求解
遞迴算是最基礎的 DP，遞迴是就是 DP 的轉移式
這邊要注意的是，通常遞迴的 DP 要有三大要素 :
- 初始值 (遞迴停止條件)
- 轉移式
- 迴圈範圍
以下舉幾個比較有名的例子
### 費氏數列
這算是最著名的遞迴公式，他的前幾項是 : $1, 1, 2, 3, 5, 8, 13, 21,\cdots$
$$
f_n=
\begin{cases}
1 & \text{, if } n = 1\text{ or } n=2\\
f_{n-1}+f_{n-2} & \text{, otherwise}
\end{cases}
$$
如果要用程式來實作也很簡單
```cpp=
int f[MXN];
void fib(int n) {
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
}
```
通常這類遞迴式 DP 需要注意以下幾點 :
- 初始化要設定好 : $\text{f}[1]=\text{f}[2]=1$
- 轉移式要推對 : $\text{f}[i] = \text{f}[i - 1] + \text{f}[i - 2]$
- 迴圈範圍要注意 : 由於第 $1$、第 $2$ 項都已經定義，第 $3$ 項以後到第 $n$ 項都還沒計算出來，因此要設定範圍 $[3, n]$
### 錯位排列數
我們再來看一個例子 :「有一個長度為 $n$ 的 permutation $p$，對每個位置 $i$ 來說，$p_i\neq i$。請問 $p$ 總共有多少種可能?」這個問題最早是歐拉和伯努力 (忘記是哪個) 推出公式，現在我們先來看看遞迴式 :
$$
D_n=
\begin{cases}
0 & \text{, if }n = 1\\
1 & \text{, if }n = 2\\
(n - 1)(D_{n-1}+D_{n-2}) & \text{, otherwise}
\end{cases}
$$
我們以後再來討論怎麼推的。在實作以前先來看清楚以下幾點 :
- 初始值 : $\text{d}[1]=0, \text{d}[2]=1$，因為遞迴式只需要前兩項就好
- 轉移式 : $\text{d}[i]=(i - 1)(\text{d}[i-1]+\text{d}[i-2])$
- 迴圈範圍 : $[3, n]$
有了這些資訊，寫程式就變簡單了!
```cpp=
int d[MXN];
void derangement(int n) {
d[1] = 0, d[2] = 1;
for (int i = 3; i <= n; i++)
d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
}
```
有了 $\text{d}[~]$，要找 $[1, n]$ 範圍內的答案都是 $O(1)$
### 組合數
相信大家都認識組合數，高中應該都有學過
$$
\binom{n}{k} = \frac{P^n_k}{k!} = \frac{n!}{k!(n-k)!}
$$
由於除法運算在數值計算上是個很差的算法，我們會希望計算可以把數值維持在整數，因此通常會考慮帕斯卡三角的遞迴式 :
$$
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
$$
把他畫出來長這樣 :
<center>
圖源 : [師大演算法筆記](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html)
</center>
來稍微觀察一下這個遞迴式 :
- 初始值 : 根據圖表，對於所有 $i$，$\text{dp}[i][0]=\text{dp}[i][i]=1$
- 轉移式 : $\text{dp}[i][j] = \text{dp}[i - 1][j - 1] + \text{dp}[i - 1][j]$，因為這是二維的，勢必要開兩層迴圈才行。除此之外，根據圖表所示，我們可以一層一層往下跑
- 迴圈範圍 : 外層 $1\sim n$，內層 $1\sim$ 對角
```cpp=
int dp[MXN][MXN];
void combination(int n, int k) {
for (int i = 0; i <= n; i++)
dp[i][0] = dp[i][i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++)
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
```
這樣的時間複雜度是 $O(n^2)$
### 卡特蘭數
卡特蘭數又稱卡塔蘭數，他有很多種推法，其中一種就是遞迴式 :
$$
C_n=
\begin{cases}
1 & \text{, if } n\ge1\\
\sum\limits_{i=0}^{n-1}C_i\cdot C_{n-1-i} & \text{, otherwise}
\end{cases}
$$
老樣子我們來觀察一下，才知道該怎麼實作 :
- 初始值 : $\text{dp}[0]=\text{dp}[1] = 1$
- 轉移式 : $\sum\limits_{j=0}^{i-1}C_j\cdot C_{n-1-j}$，這顯然需要一個 $0\sim i-1$ 的 for 迴圈 $\Rightarrow O(n)$
- 迴圈範圍 : $i$ 從 $2$ 到 $n$ 的 for 迴圈
觀察完畢!! 來實作!!
```cpp=
int dp[MXN];
void Catalan(int n) {
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
int s = 0;
for (int j = 0; j <= i - 1; j++)
s += dp[j] * dp[i - 1 - j];
dp[i] = s;
}
}
```
這樣要花 $O(n^2)$ 的時間，糟透了! 事實上還有另一種遞迴式可以支持 $O(n)$ 計算 :
$$
C_{n} = \frac{2(2n-1)}{n+1} C_{n-1}
$$
但這種需要用到除法，如果不是模運算，在計算上不是非常理想
## 走方格問題
### 問題描述
給一個 $n\times m$ 的棋盤方格，左上角 $(1, 1)$ 為起點，每次可以往右走或往下走，請問從起點走到右下角 $(n, m)$ 的方法數是多少?
<center>
</center>
### 設計 DP 轉移式
#### 轉移式
我們來觀察一下每個方格如何計算出答案。對於每個方格，都只有可能從上面或左邊走過來，因此我們可以表達成 :
$$
\text{dp}[i][j]=\text{dp}[i - 1][j] + dp[i][j - 1]
$$
#### 初始值
在起點 $(1, 1)$ 的方法數為 $1$，我們可以寫成 :
$$
\text{dp}[1][1] = 1
$$
我們觀察一下轉移式會發現，對於第 $1$ 行與第 $1$ 列不符合轉移式，因為當 $i=1$ 時，$\text{dp}[i-1][j]$ 的值未定義；當 $j=1$ 時，$\text{dp}[i][j-1]$ 的值未定義。換句話說就是，$i-1=0$ 與 $j-1=0$ 的這些位置超過範圍了!! 因此我們可以考慮以下初始化 :
$$
\text{dp}[i][1] = \text{dp}[i - 1][1]
$$
$$
\text{dp}[1][j] = \text{dp}[1][j - 1]
$$
由於這初始化也算是種轉移式，也要設定 $i$ 的範圍 $[2, n]$ 與 $j$ 的範圍 $[2, m]$
#### 迴圈範圍
因為要窮舉所有的點，所以要用兩層巢狀迴圈 :
- $i$ 的範圍為 $[2, n]$
- $j$ 的範圍為 $[2, m]$
### 程式實作
```cpp=
// 初始化
dp[1][1] = 1;
for (int i = 2; i <= n; i++) dp[i][1] = dp[i - 1][1];
for (int j = 2; j <= m; j++) dp[1][j] = dp[1][j - 1];
// 轉移
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= m; j++)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
```
這樣的時間複雜度是 $O(nm)$
### 問題變體
這種題目有個變體，就是在某些方格加上障礙物，使該格無法通行
<center>
圖源 : AtCoder DP Contest
</center>
像這種題目就需要加上 if 的判斷，只有能走的方格才能轉移
```cpp=
// 初始化
dp[1][1] = (g[1][1] == '.');
for (int i = 2; i <= n; i++){
if (can_move(i, 1))
dp[i][1] = dp[i - 1][1];
}
for (int j = 2; j <= m; j++) {
if (can_move(1, j))
dp[1][j] = dp[1][j - 1];
}
// 轉移
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= m; j++)
if (can_move(i, j))
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
```
其實不難 :smile:
## 動態規劃題目剖析
接下來要來面對 DP 最難的部分。想當年我在學 DP 時，打開題目後總是在螢幕前乾瞪眼，寫不出來。這種事很常見，好在當時同在教室中的同學們也陪我一起乾瞪眼，才伴我度過痛苦的歲月
### 理解題目
理解題目是開題後要做的第一件事，有時候可能會被奇怪的英文名詞卡住|| (那是你修練不足)||，更多時候會是不知道題目在問什麼。想要讀懂題目，必須要先知道題目的目標是什麼
競程的題目有一個毛病，就是條件會給很雜，雜到當我們想要知道要求的目標時，時常難以理解。像是「給定操作 1.2.3.$\cdots$，要你做最少的xxx並最大化ooo」這種時候當資訊量太多的時候，就需要統整一下
在這種時候，我們時常需要「寫」下我們對於題目的理解。當然，不是原話造抄，而是要翻譯成自己能理解的語言 (e.g. 畫圖、列表格、$\cdots$等)。我在大多數時候都會先用自己熟悉的數學符號來表達 ||~~(可能閒書讀多了就習慣用數學符號)~~||，像是 $\forall$、$\exists$、大於小於等於、集合操作、序列、遞迴、線性規劃等，都是我常用來表達的語言
### 估計可能的時間/空間花費
當我們看題目時，總會看到最後幾行有限制，比如說 $1\le n\le10^{5}$ 之類的。這些限制其實就是給你的提示，像是給你 :
- $1\le n\le2\times10^5$ : 大概可以在 $O(n\log n)$ 解決
- $1\le n\le 24$ : 有可能是 $O(2^n)$
- $1\le n\le10^6$ : $O(n)$ 非常安全
- $1\le n\le 100$ : 有可能可以在 $O(n^3)$ 內解決
- $1\le k\le 10^9$ : 看看有沒有其他限制比這個小，不然就想辦法離散化
$$\vdots$$
知道這些提示後，就能知道解題需要幾層迴圈、DP 要有多少狀態、用哪個演算法等等。只要抓到一個重點 **題目限制就是出題者給你最大的提示**
要注意的是，在 C/C++ 中，一個全域陣列最大可以開到 $10^7$ 這個量級。通常 Online Judge 跑 C/C++ 大概可以跑到 $10^8$ 的步驟數量 (就是你迴圈只能跑這麼多次)
### 觀察最小的問題
在理解題目後，我們要來觀察在最小的 case 時，答案會是多少，因為最小的 case 通常是可以手算的。有時候如果一個 case 不夠，可以再舉第二個、第三個 case。這些最小問題的解，很多時候是我們轉移式的停止條件 (初始值)
### 推論 DP 狀態
這塊通常是最難的，要決定 DP 的狀態，我們可以看看隨著問題變多變雜，哪些事情是會改變的，哪些不會變。要知道這些資訊，要先假設演算法執行到一半，第一步是要先釐清現在的狀態，舉例來說 :
- 位置/進度 : 陣列的前 $i$ 個元素、方格的第 $(i, j)$ 格、樹上的某個節點
- 約束條件 : 背包還剩多少容量、已經選了幾個物品
- 狀態轉向 : 上一步是往左還是往右、目前是否持有某個元素
$$\vdots$$
有了這些狀態後，就可以建立一個陣列 $\text{dp}$，可以是一維、二維或是更高維，每一個維度都代表著一個資訊
比如說我可以定義 :
- $\text{dp}[i]$ : 數列第 $i$ 項
- $\text{dp}[x][y]$ : 在地圖 $(x, y)$ 位置
- $\text{dp}[i][k][0/1]$ : 三個維度分別代表在取第 $i$ 個物品時，背包已使用空間 $k$，第 $i$ 個物品是否取用 ($0$ 或 $1$)
- $\text{dp}[i][S]$ : 在取用第 $i$ 個物品時，已經挑了集合 $S$ 中的這些物品
$$\vdots$$
這些都是常見的定義方式
### 定義轉移式
在有了狀態之後，我們可以試著改變狀態的內容，比如說從第 $i$ 個物品變成第 $i+1$ 個物品，或是從 $(x,y)$ 變成 $(x+1, y), (x,y+1)$ 等。試著調整之後看看要求的目標解會產生哪些變化，這變化就會是我們在定義轉移式的計算方法 :
- 在求費氏數列第 $n$ 項時，我們需要從第 $n-1$ 與第 $n-2$ 項取值相加
- 在走方格問題時，我們從 $(x-1,y)$ 走到 $(x, y)$ 時就發現了 $\text{dp}[x-1][y]$ 的方法數會被加入 $\text{dp}[x][y]$ 的方法數
- 在求[樹上每個節點的高度](https://hackmd.io/@ShanC/special-vertices-on-tree#%E9%AB%98%E5%BA%A6-Height)時，我們會從所有子節點中取最大值 $+1$ 存入父節點
$$\vdots$$
這些都是常見的例子
## 例題說明 1 : [超級馬拉松賽](https://zerojudge.tw/ShowProblem?problemid=b589)
題目敘述應該要你自己先看完，有了自己的理解還能懂這在講什麼
### 題目敘述
給一跑道切分成 $n$ 段，目標是要從左 (第 $1$ 段) 跑到右 (第 $n$ 段)。每一段 $i$ 在正常時間內跑完都可以獲得分數 $p_i$，跑特別快就可以獲得 $2\cdot p_i$，跑太慢就會獲得 $0$ 分。每段可以選擇速度是快、正常還是慢，這段快的話下段合就只能慢，請問跑完的最大分數為何?
- $1 \le n \le 40$
- $10\le p_i\le 100$
### 想法
簡單來說就是我們要最大化函數 :
$$
f(c_1, c_2, \cdots, c_n)=c_1p_1+c_2p_2+\cdots c_np_n=\sum\limits_{i=1}^{n}c_i p_i\\
$$
其中 $c_i\in \{0, 1, 2\}$，限制為 :
$$
\text{if }c_i=2\text{, then } c_{i+1}=0 \quad (1\le i\le n)
$$
這裡可以變動的數值只有兩個
- 第 $i$ 段
- 跑快、正常、跑慢
設狀態 $\text{dp}[i][0/1/2]$ : 跑到目前第 $i$ 段時，速度為跑快 (2)、正常 (1) 或跑慢 (0) 的最大分數
不難發現，當目前跑到第 $i$ 段時，唯一有關連的就是跑第 $i-1$ 段時的最大值，我們可以分成幾種狀況 :
- 若目前第 $i$ 段是跑快 (2)，則前一段 $i-1$ 肯定不會是跑快 (2)，因此只會是正常跑 (1) 或跑慢 (0) 的最大值，再加上 $2\cdot p_i$
$$\text{dp}[i][2]=\max\{\text{dp}[i-1][0], \text{dp}[i-1][1]\}+2\cdot p_i$$
- 若目前第 $i$ 段是正常跑 (1)，則前一段 $i-1$ 肯定不會是跑快 (2)，因此只會是正常跑 (1) 或跑慢 (0) 的最大值，再加上 $p_i$
$$\text{dp}[i][1]=\max\{\text{dp}[i-1][0], \text{dp}[i-1][1]\}+p_i$$
- 若目前第 $i$ 段是跑慢 (0)，則前一段 $i-1$ 三種狀態都有可能是我們要的資訊。記得這裡不用加任何的值
$$\text{dp}[i][1]=\max\{\text{dp}[i-1][0], \text{dp}[i-1][1], \text{dp}[i-1][2]\}$$
最後，觀察道第 $0$ 段 (還沒開始跑) 的時候，答案是 $0$。因此初始化為 $0$
至此，整個 DP 的定義流程就完成了!
### 程式實作
```cpp=
int dp[MXN][3];
for (int i = 1; i <= n; i++) {
dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + p[i];
dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + 2 * p[i];
}
cout << *max_element(dp[n].begin(), dp[n].end()) << '\n';
```
時間 : $O(3\cdot n)$
## 例題說明 2 : [11069 - A Graph Problem](https://zerojudge.tw/ShowProblem?problemid=d389)
### 題目敘述
給一個由 $n$ 個節點，組成的鏈圖，請問此鏈圖的極大[獨立集](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem#%E7%8D%A8%E7%AB%8B%E9%9B%86-Independent-Set)有幾種?
- $1\le n\le 76$
||雖然 $n$ 很小，但是根據我的測試，這題可以 $O(n)$||
### 想法
這題有點難觀察出規律，所以可以先窮舉長度為 $n$ 的鏈圖 :
- $n=1$ : $\{1\}$
- $n=2$ : $\{1\}, \{2\}$
- $n=3$ : $\{2\}, \{1, 3\}$
- $n=4$ : $\{1,3\}, \{2,4\}, \{1,4\}$
把元素是否在集合中叫做取/不取，我們可以觀察出幾個現象 :
- 若第 $i$ 項取了，第 $i-1$ 項就不能取、第 $i-2$ 項可取可不取
- 若第 $i-2$ 不取，那第 $i-3$ 項就一定要取，否則違反「極大」的規則
- 若第 $i-2$ 取了，那就可喜可賀!!
- 若第 $i$ 項不取，則第 $i-2$ 就一定要取
有了以上就可以定義狀態了，定義 $\text{dp}[i][0/1]$ 為目前取長度為 $i$ 時，第 $i$ 項是否要取。透過以上觀察可以得出以下轉移式 :
$$
\begin{split}
&\text{dp}[i][0] = \text{dp}[i - 1][1]\\
&\text{dp}[i][1] = \text{dp}[i - 2][1] + \text{dp}[i-3][1]\\
\end{split}
$$
### 程式實作
```cpp=
// 如果長度 i，but 不拿 i
dp[1][0] = 0, dp[1][1] = 1; // 0: {0}, 1: {1}
dp[2][0] = 1, dp[2][1] = 1; // 0: {1}, 1: {2}
dp[3][0] = 1, dp[3][1] = 1; // 0: {2}, 1: {1, 3}
// dp[4][0] = 1, dp[4][1] = 2; // 0: {1, 3}, 1: {2, 4}, {1, 4}
for (int i = 4; i <= n; i++) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = dp[i - 2][1] + dp[i - 3][1];
}
cout << dp[n][0] + dp[n][1] << '\n';
```
時間 : $O(n)$
好像有看到其他種寫法，但我沒仔細研究
## 後記
### 遺珠之憾
這些 DP 可以延伸的東西還蠻多的，寫越多越發現很多東西都塞不下這篇。像是背包問題的各種變體、換零錢問題跟加法組合學的關係，這些我其實都想多講一點，因此那些篇章我想要獨立出去，而不是放在這裡。還有像是 LIS、LCS 等著名的 DP 問題，放在這裡實在太跳痛了，因為它很難用這邊介紹的方法「觀察」出來
撰寫本篇的目的是為了介紹動態規劃的思想，其他講義或筆記我都覺得對初學者不友善。我認為以上這些例子才是最適合初學者學的東西，而不是那些背包、零錢或 LCS
### DP 五步法?
對我知道有這個東西，其實就是以下 :
1. 構造問題
2. 定義狀態
3. 求解小規模的簡單問題
4. 狀態轉移方程式
5. 判斷複雜度
但根據我的經驗，這種需要觀察力的題目不適合照順序來機械化的處理，有時候通靈反而會更快一點。我這篇不照五步法是因為我覺得 DP 只要掌握原則即可，不要拘泥於步驟
### 其他
在寫這篇的同時，我也在準備校內競程講義，由於我不是負責教 DP 的講師，我沒有機會在學弟妹面前講我對 DP 的想法。在規劃自己的筆記要怎麼寫時，我發現自己對 DP 看法、切入點跟其他人都很不同。在我的經驗中，那些 DP 問題都經常出現在別的領域的課本中。像是計算理論、組合學、隨機演算法都可以經常看到這些 DP 問題的影子。說實話我覺得開篇直接講背包、LCS、LIS、Edit distance 等問題容易讓人失焦在表格怎麼表示、code 怎麼跑等問題，DP 作為解題技巧的本質都是到很晚才說到，所以我決定自己寫我覺得脈絡比較合理的筆記
## 題目練習
[CSES Christmas Party](https://cses.fi/problemset/task/1717/) (錯排裸題)
[Zerojudge d443. 10497 - Sweet Child Makes Trouble](https://zerojudge.tw/ShowProblem?problemid=d443) (錯排裸題)
[Zerojudge d524. 10599 - Robots(II)](https://zerojudge.tw/ShowProblem?problemid=d524) (其實是 DP on DAG)
[Zerojudge d198. 00825 - Walking on the Safe Side](https://zerojudge.tw/ShowProblem?problemid=d198) (方格題變一下而已)
[AtCoder Educational DP Contest H - Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h) (方格題)
[2024 TOPC B. Business Magic](https://codeforces.com/gym/105383/problem/B) (對，TOPC 也會出這種題)
[AtCoder Beginner Contest 443E - Climbing Silver](https://atcoder.jp/contests/abc443/tasks/abc443_e)
----
## 參考資料
[Wikipedia - Derangement](https://en.wikipedia.org/wiki/Derangement)
[台師大演算法筆記 - Dynamic Programming](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2026/2/1
Sign in with Wallet
Connect another wallet