【C++】競程筆記（DP：動態規劃）

程式碼範例參考：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，可以趁機推敲一下就知道這有可能就是費氏數列的類似做法。

因此我們可以寫下以下的程式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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，將計算完的結果記起來，最後想要哪階的答案時就直接把它給叫出來。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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

這邊務必記得 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

  • 寛度為 1 單位的牆只有一種花樣—就是讓磚塊直立。
  • 長度為 2 的牆有 2 種花樣—兩個平躺的磚磈疊在一起以及兩個直立的磚塊併在一起。
  • 長度為 3 的牆有三種花樣。

長度為 4 的牆你可以找出幾種花樣？那長度為 5 的牆呢？

你的工作是要寫一個程式，給它牆的長度，它就算出這道牆可以有幾種花樣。

輸入說明：

你將程式會收到一連串的整數，一行一個，每個整數代表牆的長度。牆的最大長度為 50。

輸出說明：

對於每個輸入的牆長度，你要輸出這道牆的花樣數量，每個數字單獨一行。

範例輸入：

1
2
3
4
1
2
3
0

範例輸出：

1
2
3
1
2
3

解題思路：

那長度為四的牆你可以推算一下，第一個情況肯定是四塊直立的在一起，那第二個情況可以分成兩個直的、兩個橫的，第三個情況就是上一個的相反，然後第四個情況則是兩個直的夾著一個橫的，最後一個情況則是四個橫的可以堆在一起。

那這部分可以畫圖看看就知道了，最後我們就知道長度為四的牆總共有五種花樣。

將長度為一的到長度為四的數字擺在一起看，你就會發現有端倪阿，這不就是費氏數列的長相嗎？所以就可以寫程式了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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

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

image

▲裝滿長度為 2 的盒子的 5 種方法。

輸入說明：

輸入的開始有一個 $t$ ，表示有幾個不同長度的盒子。接下來的 $t$ 行每行有一個整數 $n$ ( $1 \leq n \leq 40$ )。

輸出說明：

相對於每個 $n$ 輸出一行，該行中的數字為有幾種方法可以用上述的蛋糕裝滿一個 $2 \times n$ 的盒子。輸出的數字保證小於 $1018$ 。

範例輸入 #1：

1
2
3
2
1
2

範例輸出 #1：

1
2
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
[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）的情況了。

然後就可以開始寫程式了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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$ ，相信不用我講也知道這是啥了吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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，因為可能會有溢位問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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）按「最後一個元素的狀態」分類。

以下是思考的模板，僅供參考：

1
2
3
4
5
6
7
如果最後一個元素是 [狀態 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：

  • 漏掉某些情況。
  • 重複計算。
  • 分類標準不一致。

第五步：寫出遞迴式。

格式基本上都長得一樣啦：

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

然後記得檢查邊界條件。