---
# System prepended metadata

title: 【C++】競程筆記（DP：動態規劃）
tags: [程式設計, C++, DP, 競程, 演算法, CP]

---

# 【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 撰寫遞迴式

在高中的時候應該就有教過這個東西了，以爬樓梯舉例的話，完整遞迴式就是：

![image](https://hackmd.io/_uploads/Hkx-bMqCel.png)

這邊務必記得 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 的翻譯：

如果我們要用常見的長度為高度兩倍的磚塊建一道磚牆，並且牆的高度為兩個單位，根據牆的長度，我們可以建出不同數量的花樣。從圖一我們可以看出：

![image](https://hackmd.io/_uploads/Hyhaf7jAex.png)

* 寛度為 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 想知道有幾種不同的方式可以把蛋糕裝滿一個特定尺寸的盒子。你能幫他嗎？

![image](https://hackmd.io/_uploads/r1-A9BiCee.png)

▲左圖為蛋糕的尺寸，右圖為裝滿長度 6 的盒子的一種方法。

![image](https://hackmd.io/_uploads/HJDRqSo0ge.png)

▲裝滿長度為 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，再把遞迴式代進去這兩個最小子問題，去驗證你的遞迴式是正確無誤的。

然後記得檢查邊界條件。

