# 【C++】競程筆記（DP：動態規劃）
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
## 什麼是動態規劃（DP, Dynamic Programmnig）
動態規劃（Dynamic Programming, DP）是一種解決複雜問題的演算法技巧，核心概念是將大問題拆解成小問題，然後把小問題的答案給存起來，避免重複計算。
DP 的核心精神就是「空間換時間」的概念，會用到記憶法（memoization）的概念去記下小問題。
舉個栗子，在刷題的時候，如果每次遇到相同的計算題，都要重算一遍會很浪費時間，不如把答案記在草稿紙上，在有需要的時候再拿起來複習一下就好了。
## 爬樓梯問題
爬樓梯問題是每個初學 DP 的人都會遇到的第一道問題。
Problem link : https://oj.ntucpc.org/problems/17
Description :
小明現在需要爬 $N$ 階的樓梯，他可以一次爬一階或兩階，請問他有幾種方法？
舉例來說，假設小明需要爬三階的樓梯，那他有以下三種爬法：
* 每次都只爬一階，也就是依序爬上第一階、第二階再到第三階。
* 先爬第一階後，直接一口氣爬到第三階。
* 直接爬到第二階後，再爬到第三階。
Input Format :
輸入只有一行一個正整數 $N$ ，代表小明要爬的階梯數。
Output Format :
輸出小明爬到第 $N$ 階的方法數。
解題思路：
爬一階的方法數只有 1，而爬兩階的方法數是 2，因為可以連續爬兩次 1 階跟一次爬兩階，最後爬三階的方法數是 3，可以趁機推敲一下就知道這有可能就是費氏數列的類似做法。
因此我們可以寫下以下的程式：
```cpp=
#include <iostream>
using namespace std;
using ll = long long;
ll solve(ll n){
if (n <= 1) return 1;
return solve(n - 1) + solve(n - 2);
}
int main(){
ll n;
cin >> n;
cout << solve(n);
return 0;
}
```
然後你就會發現他 TLE 了，原因是因為每當 $n - 1$ 的情況就會窮舉兩種情況，而 $n - 2$ 也窮舉兩個情況，最後就會得到醜到不行的時間複雜度 $O(2^n)$ 。
那這時候就要用到 DP 的技巧了，也就是所謂的 memoization，將計算完的結果記起來，最後想要哪階的答案時就直接把它給叫出來。
```cpp=
#include <iostream>
using namespace std;
using ll = long long;
ll dp[90] = {0};
ll solve(ll n){
if (n <= 1) return 1;
if (dp[n] != 0) return dp[n]; // 算過了，直接回傳答案
dp[n] = solve(n - 1) + solve(n - 2);
return dp[n];
}
int main(){
ll n;
cin >> n;
cout << solve(n);
return 0;
}
```
## 如何在 DP 找子問題？
首先就是要**尋找問題的遞迴關係**（recurrence）。
DP 的關鍵是把大問題拆成小問題。拆法是觀察問題的結構，確定一個狀態（state）來表達「部分解」，然後推導出如何透過較小規模的狀態推算出較大規模的狀態。如費氏數列當中，他的第 $n$ 項是由第 $n - 1$ 加上 $n - 2$ 所組成，這兩個就是規模更小的子問題。
再來則是**利用重疊子問題**（Overlapping Subproblems）。
原問題被拆出的子問題往往會重複出現，這時將子問題的答案存起來避免重複計算是 DP 的優勢。這些子問題的大小一般比原問題小，是問題解的一部分。
如一般遞迴的呼叫效率是最差的，會不斷重複呼叫，這時候用 DP 就可以把關鍵的幾個子問題用 memoization 的方式記起來，提高演算法的效率。
若沒有重複子問題就不需要 DP 了，因為直接呼叫即可，何必記憶化。
最後是**狀態定義**（state definition）。
定義狀態就是定義子問題，比如「 $dp[i]$ 表示解決到第 $i$ 個子問題的答案」。子問題的大小一般會比原問題小，比如子問題 $i$ 比較容易計算，然後遞推到 $i + 1$ 等。
像上面爬樓梯的 dp 程式碼， `dp[n] = solve(n - 1) + solve(n - 2);` 就定義了一個 dp 狀態。
### 如何處理最簡單子問題？
第一個肯定會定義他的基本狀態（Base Case），動態規劃必須設定最簡單的子問題的答案，即「基本」狀態。這些初始狀態沒有更小的子問題可以拆，答案通常是已知或容易計算的。像是費氏數列的最開始 $F(0) = 1$ 以及 $F(1) = 1$ 就是基本狀態。在不斷遞迴拆解子問題的時候，拆到沒東西可以拆就會遇到基本狀態。
最後是決定邊界條件（Boundary Condition）確認計算順序時，從最簡單子問題開始算起，逐漸往複雜子問題填表，避免遞迴無窮。
## 為 DP 撰寫遞迴式
在高中的時候應該就有教過這個東西了，以爬樓梯舉例的話，完整遞迴式就是：
這邊務必記得 DP 或不可缺的元素是基本狀態（Base case），也就是當 $n \leq 1$ 時回傳的值。
## 爬樓梯的變化題：Brick Wall Patterns
Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=841
Zerojudge：https://zerojudge.tw/ShowProblem?problemid=d038
PDF Source：https://onlinejudge.org/external/9/900.pdf
這邊直接放 Zerojudge 的翻譯：
如果我們要用常見的長度為高度兩倍的磚塊建一道磚牆，並且牆的高度為兩個單位，根據牆的長度，我們可以建出不同數量的花樣。從圖一我們可以看出：
* 寛度為 1 單位的牆只有一種花樣—就是讓磚塊直立。
* 長度為 2 的牆有 2 種花樣—兩個平躺的磚磈疊在一起以及兩個直立的磚塊併在一起。
* 長度為 3 的牆有三種花樣。
長度為 4 的牆你可以找出幾種花樣？那長度為 5 的牆呢？
你的工作是要寫一個程式，給它牆的長度，它就算出這道牆可以有幾種花樣。
**輸入說明**：
你將程式會收到一連串的整數，一行一個，每個整數代表牆的長度。牆的最大長度為 50。
**輸出說明**：
對於每個輸入的牆長度，你要輸出這道牆的花樣數量，每個數字單獨一行。
**範例輸入**：
```
1
2
3
0
```
範例輸出：
```
1
2
3
```
解題思路：
那長度為四的牆你可以推算一下，第一個情況肯定是四塊直立的在一起，那第二個情況可以分成兩個直的、兩個橫的，第三個情況就是上一個的相反，然後第四個情況則是兩個直的夾著一個橫的，最後一個情況則是四個橫的可以堆在一起。
那這部分可以畫圖看看就知道了，最後我們就知道長度為四的牆總共有五種花樣。
將長度為一的到長度為四的數字擺在一起看，你就會發現有端倪阿，這不就是費氏數列的長相嗎？所以就可以寫程式了。
```cpp=
#include <iostream>
using namespace std;
long long dp[60] = {0};
long long solve(int n){
if (n <= 1) return 1;
if (dp[n] != 0) return dp[n];
dp[n] = solve(n - 1) + solve(n - 2);
return dp[n];
}
int main(){
int n;
while (cin >> n && n){
cout << solve(n) << "\n";
}
}
```
## Uva 11310 - Delivery Debacle
Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2285
Zerojudge：https://zerojudge.tw/ShowProblem?problemid=d054
PDF Source：https://onlinejudge.org/external/113/11310.pdf
這邊一樣直接放 Zerojudge 翻譯：
Wolfgang Puck 有兩個很特別的習慣：
- I. 他只做兩種形狀的蛋糕。一種是面積為一單位的方形，另一種是面積為三單位的 L 形。
- II. 他只用特定尺寸的盒子來裝蛋糕。這些盒子的寛度都是二單位，但各種不同長度都有。
有一天，Wolfgang 想知道有幾種不同的方式可以把蛋糕裝滿一個特定尺寸的盒子。你能幫他嗎？
▲左圖為蛋糕的尺寸，右圖為裝滿長度 6 的盒子的一種方法。
▲裝滿長度為 2 的盒子的 5 種方法。
**輸入說明**：
輸入的開始有一個 $t$ ，表示有幾個不同長度的盒子。接下來的 $t$ 行每行有一個整數 $n$ ( $1 \leq n \leq 40$ )。
**輸出說明**：
相對於每個 $n$ 輸出一行，該行中的數字為有幾種方法可以用上述的蛋糕裝滿一個 $2 \times n$ 的盒子。輸出的數字保證小於 $1018$ 。
**範例輸入 #1**：
```
2
1
2
```
**範例輸出 #1**：
```
1
5
```
解題思路：
寬度固定是 2，而當長度為 1 的時候，也就是 $2 \times 1$ ，能放的組合只有兩種，L 型跟單位 1 的正方形，而這邊能放的只有兩個正方形，所以最後只有一種組合。
長度為 2 的時候， $2 \times 2$ ，必定是由一個 L 型加上一個正方形所組成的圖形，經過四次旋轉會得到不同的結果，而最後是兩個長度為 1 的解法（實際上只算方法數 1），因此 4+1 = 5。
疑？那這時候就可以得到 $f(n) = f(n - 1) + 4 \times f(n - 2)$ 的結果了。
但是還少了 >= 3 的結果，可以先試想一下 n = 3 的情況是怎麼樣的，n = 3 就是 $2 \times 3$ ，這樣子會有兩種可能的排列方式，然後先讓我畫個簡單的圖給各位看。
```
[1][2][3]
[4][5][6]
```
- 第一種方式：兩個 L 型分別佔滿 `[2][1][4]`、`[3][6][5]`。
- 第二種方式：相較前面方式把垂直改成水平的，也就是 `[1][4][5]`、`[2][3][6]`。
最後會得到 $f(n) = f(n - 1) + 4 \times f(n - 2) + 2 \times f(n - 3)$ 的遞迴式。
細心的你代回去 n = 2 的情形，會發現答案是錯的，那這時候就要考慮把 n = 2 納入基本狀態（Base case）的情況了。
然後就可以開始寫程式了：
```cpp=
#include <iostream>
using namespace std;
long long dp[60] = {0};
long long solve(int n){
if (n <= 1) return 1;
if (n == 2) return 5;
if (dp[n] != 0) return dp[n];
dp[n] = solve(n - 1) + 4*solve(n - 2) + 2*solve(n - 3);
return dp[n];
}
int main(){
int t;
cin >> t;
while (t--){
int n;
cin >> n;
cout << solve(n) << "\n";
}
}
```
## 習題練習
### 1476. 會議中心（Room）
Problem Source：https://tioj.ck.tp.edu.tw/problems/1476
解題思路：
觀察測資所說的每次擴充新增的正方形邊長，即可求得：
- 第 0 次：1
- 第 1 次：1
- 第 2 次：2
- 第 3 次：3
- 第 4 次：5
- 第 5 次：8
把這些寫成一個數列： $1, 1, 2, 3, 5, 8$ ，相信不用我講也知道這是啥了吧。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
vector <long long> dp(50);
long long solve(int n){
if (n <= 1) return 1;
if (dp[n] != 0) return dp[n];
dp[n] = solve(n - 1) + solve(n - 2);
return dp[n];
}
int main(){
int n;
cin >> n;
cout << solve(n);
}
```
### Uva 11069 - A Graph Problem
Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2010
Zerojudge：https://zerojudge.tw/ShowProblem?problemid=d389
PDF Source：https://onlinejudge.org/external/110/11069.pdf
解題思路：
題目給了兩道規則：
1. 不能相鄰，也就是像是 `{1, 2}` 這種集合是非法的。
2. 有空位不能不填，如 n = 5 的情況，`{1, 5}` 這種集合也是非法的，因為中間有個 3 沒有被考慮進去。
這邊可以設想兩種情況：
1. 最後一位有人填，也就是第 n 個位置有人填走了。這就表示說 n - 1 是不能填人的，因為它相鄰，所以就剩 n - 2 了。因此我們得到第一個遞迴式的線索 $f(n - 2)$ 。
2. 最後一位沒人填，n 跟 n - 1（n - 1 填了違反第一條規則）沒人填，根據第二條規則，第 n - 2 是一定要填人的，因為 n - 2 你不填你就違反規則了。如果第 n - 2 有人，那第 n - 3 肯定空的，在此之前的 n - 3 的座位就是安排的重點了，因此得到最後一個遞迴式的線索 $f(n - 2)$ 。
最後得到完整遞迴式： $f(n) = f(n - 2) + f(n - 3)$ 。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
vector <long long> dp(80);
long long solve(int n){
if (n <= 1) return 1;
if (n == 2) return 2;
if (n == 3) return 2;
if (dp[n] != 0) return dp[n];
dp[n] = solve(n - 2) + solve(n - 3);
return dp[n];
}
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
while (cin >> n){
cout << solve(n) << "\n";
}
}
```
### TOI2009 第一題：路徑問題
Problem Source：https://zerojudge.tw/ShowProblem?problemid=b229
解題思路：
一樣的套路，先求出遞迴式。
題目告訴你 N = 1 的時候是 3，因為只有左右跟上這三種選擇而已。
N = 2 的時候，首先把 N = 1 算的 3 加進來，因為也是左右上三種選擇（N = 2 的話就是往左右上走兩格），然後固定往右的選擇，會發現有上下兩種，固定往左也是只有兩種，最後 3 + 2 + 2 得到 7。
ok 我們求出了前兩項的 base case 了，那接下來討論遞迴式怎麼辦吧：
1. 最後一步往右或往上。
- 試想一下或畫個圖，這兩個方向都不會回到之前走過的點。
- 前 $n-1$ 步可以是任意長度為 $n-1$ 的合法路徑。
- 兩個方向各貢獻 $f(n-1)$ ，因此總共貢獻 $2·f(n-1)$ 。
2. 最後一步往左。
- 往左代表「回頭」，所以倒數第二步必定是往右，否則左邊的格子已經被訪問過，會違反相異邊的規則，因此最後兩步形成右到左的組合（相當於往返）。
- 前面只需要 $n-2$ 步的路徑，再加上這個往返，因此最後貢獻 $f(n-2)$ 。
最後就會得到遞迴式 $f(n) = 2 \cdot f(n - 1) + f(n - 2)$ 囉。
題目注意使用 unsigned long long，因為可能會有溢位問題。
```cpp=
#include <iostream>
using namespace std;
using ull = unsigned long long;
ull dp[55] = {0};
ull solve(int n){
if (n == 1) return 3;
if (n == 2) return 7;
if (dp[n] != 0) return dp[n];
dp[n] = 2 * solve(n - 1) + solve(n - 2);
return dp[n];
}
int main(){
int n;
cin >> n;
cout << solve(n);
}
```
## 總結：找 DP 遞迴式的六大步
解 DP 題目時最注重的就是細心程度，所以一定要仔細反覆閱讀題目，並 get 到題目的重點是什麼，要考慮到 edge case 以及 base case，接著才能進一步解題。
---
第一步：先算小的 case，去觀察數列。
做法：用暴力法或手算計算 $n=1, 2, 3, 4, 5\cdots$ 的答案，記錄成數列，觀察是否有明顯規律。
找規律可以計算相鄰項的關係（舉例而已，還是要根據題目情況調整 $n$ ）：
* $f(n) - f(n-1) = ?$ （差）
* $f(n) / f(n-1) = ?$ （比）
* $f(n) = ? × f(n-1) + ? × f(n-2)$ （線性組合）
---
第二步：定義狀態，確認子問題。
1. 一個問題是什麼？
- 通常是 $f(n) =$ 規模為 $n$ 的問題的答案數。
- 有時需要多維 $f(n, state) =$ 在某個狀態下，規模為 $n$ 的答案。
2. 子問題有哪些？
- $f(n-1), f(n-2), f(n-3)\cdots$ 等較小規模。
- 若知道所有小問題的答案，能不能推出大問題？
---
第三步：分類討論最後一步。
有三種常見的分類方式如下：
（A）按「最後一個元素的狀態」分類。
以下是思考的模板，僅供參考：
```
如果最後一個元素是 [狀態 A]：
→ 那前面的問題變成什麼？
→ 對應到哪個子問題？
如果最後一個元素是 [狀態 B]：
→ 那前面的問題變成什麼？
→ 對應到哪個子問題？
```
（B）按「最後幾個元素的組合」分類。
以習題兩題作為例子：
圖形問題：看最後 2-3 個座位的組合。
* 最後 0 個空位（ $n$ 有人）→ $f(n-2)$
* 最後 1 個空位（ $n$ 空、 $n-1$ 有人）→ $...$
* 最後 2 個空位（ $n, n-1$ 都空）→ $f(n-3)$
路徑問題：最後兩步的方向組合。
* 最後兩步是「右到左」→ $f(n-2)$
* 最後一步是「右」或「上」→ $2×f(n-1)$
（C）按「到達當前狀態的方式」分類。
以爬樓梯舉例：
- 從第 $n-1$ 階跨 $1$ 階 → $f(n-1)$
- 從第 $n-2$ 階跨 $2$ 階 → $f(n-2)$
---
第四步：反覆思考。
在做 DP 題的時候可以給自己心中一個 checklist：
* 所有可能情況都考慮到了嗎？
* 不同情況之間是否重疊？（不要重複計算）
* 每種情況能清楚對應到某個子問題嗎？
* 邊界條件有處理到嗎？
常見錯誤的 checklist：
- 漏掉某些情況。
- 重複計算。
- 分類標準不一致。
---
第五步：寫出遞迴式。
格式基本上都長得一樣啦：
```
f(n) = [情況1的貢獻] + [情況2的貢獻] + ...
```
貢獻的常見形式：
- 計數問題：`係數 × f(n-k)`
- 例： $f(n) = 2×f(n-1) + f(n-2)$
- 最佳化問題： $max/min{f(n-k) + cost}$
- 例： $f(n) = max{f(n-1), f(n-2) + a[n]}$
那最後最重要的就是一定要寫下 base case。
---
第六步：驗證。
你要先手算出來非 base case 的情況，像是 n = 3 跟 n = 4，再把遞迴式代進去這兩個最小子問題，去驗證你的遞迴式是正確無誤的。
然後記得檢查邊界條件。
Sign in with Wallet
Connect another wallet