【C++】競程筆記（DP：狀態跟轉移）

題目範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

非線性遞迴題型

481 . [Tutorial] 別離太遠 續

Problem Source：https://oj.ntucpc.org/problems/481

這題要求的不是方法數，而是「最大值」。

這題的上一題已經知道要怎麼求方法數了，結果就是一個費氏數列，而這次要求的是讓每個人的能力值總和到最大，那該怎麼求呢？

遞迴式長得差不多，先定義 base case：

  • $a_1, n = 1$
  • $a_1 + a_2, n = 2$

剩下的情況可以寫成 $max(f(n - 1), f(n - 2)) + a_n$ ，因為要最大化能力值，所以從第 n 個的前兩位（編號差不能超過 2）挑出最大的那個。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main(){
    int N;
    cin >> N;
    
    vector <ll> a(N + 1);
    for (int i = 1; i <= N; ++i) cin >> a[i];
    
    vector <ll> dp(N + 1);
    
    if (N >= 1) dp[1] = a[1];
    if (N >= 2) dp[2] = a[1] + a[2];
    
    for (int i = 3; i <= N; ++i)
        dp[i] = a[i] + max(dp[i - 1], dp[i - 2]);
    
    cout << dp[N];
}

描述動態規劃演算法的形狀

動態規劃演算法會有很重要的三元素：

  • 狀態
  • 轉移
  • 初始狀態

狀態（State）

狀態是對問題在某一個特定階段的描述或快照（Snapshot）。通常由一個或多個變數組成，用來代表當前子問題的解。

像是在當說「於狀態 $i$ 」 的時候，意思就是已經解決規模為 $i$ 的子問題，並將這結果存在變數當中（應該是陣列的某個元素）。

用數學表示則是用陣列來表示一個狀態： $dp[i]$ 或多維 $dp[i][j]$ 。

用先前爬樓梯的例子來說，假設爬 $N$ 階樓梯，則定義 $dp[i]$ 為「爬到第 $i$ 階樓梯的方法數」，而 $dp[i]$ 就是狀態。當求出 $dp[5]$ 時，就知道爬到第 5 階有幾種走法。

:::info
狀態就是求解某個子問題的過程，會告訴自己現在在哪個階段？答案存在哪？
:::

轉移（Transition）

轉移是狀態之間的「關係式」，如何從一個或多個「已知的小狀態」推導出「當前的大狀態」。

由轉移產生的變化寫成數學式後，也就稱之為轉移式。

一樣從爬樓梯來舉例，爬樓梯的規則是一次只能爬 1 階或 2 階，若要到達第 $i$ 階，最後一步只有兩種可能：

  • 從第 $i-1$ 階爬 1 步上來。
  • 從第 $i-2$ 階爬 2 步上來。

因此可得到轉移式是 $dp[i] = dp[i - 1] + dp[i - 2]$

初始狀態（Initial State / Base Case）

初始狀態（也稱邊界條件）是整個遞迴或填表過程的起點，是最小的子問題，不需要經過計算，能直接知道答案。

初始狀態是很重要的狀態，沒有這東東，遞迴就會無限遞迴下去，然後電腦就會炸開。

同樣以爬樓梯來舉例，由於求出的轉移式是 $dp[i] = dp[i - 1] + dp[i - 2]$ ，有 $i - 1$ 跟 $i - 2$ 這兩個因素，可以手動設定初始狀態：

  • $dp[0] = 0$
  • $dp[1] = 1$

DP 三步法

  1. 定義狀態
  2. 找出轉移式
  3. 定義初始狀態

e.g. 1 : ZJ b589. 超級馬拉松賽

Problem Source：https://zerojudge.tw/ShowProblem?problemid=b589

首先定義狀態。

對於第 $i$ 條路徑，小愛只有兩種選擇：

  1. 正常跑
    • 得 $P_i$ 分。
    • 下條路徑 $(i + 1)$ 可以正常進行路徑決策。
    • 總分累計： $P_i + dp[i + 1]$
  2. 加速跑
    • 得 $2 \times P_i$ 分。
    • 下條路徑 $(i + 1)$ 要休息，得 0 分，所以下次能做的路徑決策是 $(i + 2)$ 。
    • 總分累計： $2 \times P_i + dp[i + 2]$

令 $dp[i]$ 是從第 $i$ 條路徑開始，一直跑到最後第 $n$ 條路徑所能獲得的最大總分。

第二個就是找出轉移式，根據前面的定義可以寫出

第三個則是定義初始狀態，若當 $i > n$ 時（超出路徑範圍），得分為 0，即 $dp[n+1] = 0, dp[n+2] = 0$。

這題採用由後往前推的方法會比較好做，如果用由前面往後推的話，可以剛好跑完第 $n$ 關結束，也可以在第 $n-1$ 關加速直接衝過終點（跑到虛擬的 $n+1$ 關），最後的答案會是 $max(dp[n], dp[n+1])$ ，要多檢查一步。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    while (cin >> n && n != 0){
        vector <int> P(n);
        for (int i = 0; i < n; ++i) cin >> P[i];
        
        vector <int> dp(n + 2, 0);
        
        for (int i = n - 1; i >= 0; --i){
            int normal = P[i] + dp[i + 1];
            int accelerate = 2 * P[i] + dp[i + 2];
            dp[i] = max(normal, accelerate);
        }
        
        cout << dp[0] << '\n';
    }
}

Generic Cow Protests

Problem Source：https://www.luogu.com.cn/problem/P1569

  1. 定義狀態：
    • 令 $S[i]$ 為前 $i$ 頭乳牛的理智度總和（ $S[0] = 0, S[i] = a_1 + a_2 + \cdots + a_i$ ）
    • 定義 $dp[i]$ 為考慮前 $i$ 頭乳牛，最多能分成的組數。
      • 如果前 $i$ 頭乳牛無法被合法分割，則 $dp[i] = -\infty$。
  2. 找出轉移式：

在這類「將序列切成若干段」的題目有一個常見的轉移招數：那就是枚舉最後一段的長相為何。
by NTUCPC Guide

對於第 $i$ 頭乳牛，得要窮舉上一個分組的結束位置 $j$ （其中 $0 \le j < i$）。

:::info
窮舉 $j$ 是為了決定最後一組的範圍，並利用算好的舊答案推出新答案。
:::

如果從第 $j+1$ 頭到第 $i$ 頭乳牛這一組的理智度總和是非負的話，且前 $j$ 頭乳牛已經有合法的分組（$dp[j] \neq -\infty$），則可將 $j$ 轉移到 $i$。

區間和條件：第 $j+1$ 到 $i$ 的和為 $S[i] - S[j]$，而題目要求 $S[i] - S[j] \ge 0$，即 $S[i] \ge S[j]$。

由於希望組數是要最多的，因此在所有滿足條件的 $j$ 中取最大值並加 1。

限制條件是：

  • $S[j] \le S[i]$ （當前小組和非負）
  • $dp[j] \neq -\infty$ （前 $j$ 個可以合法分組）
  1. 初始狀態：就是 $dp[0] = 0$

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

const int INF = -1e9;

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 前綴和
    vector<long long> S(n + 1, 0);
    for (int i = 1; i <= n; ++i) S[i] = S[i - 1] + a[i];

    vector<int> dp(n + 1, INF);

    dp[0] = 0;

    for (int i = 1; i <= n; ++i)
        // 窮舉上一個分組的結束點 j
        for (int j = 0; j < i; ++j)
            if (dp[j] != INF && (S[i] - S[j] >= 0)) 
                dp[i] = max(dp[i], dp[j] + 1);
    if (dp[n] > 0) 
        cout << dp[n] << endl;
    else
        cout << "Impossible" << '\n';

    return 0;
}

股票買賣 V

Problem Source：https://www.luogu.com.cn/problem/U425829

  1. 定義狀態

定義 $dp[i]$ 為：在第 $i$ 天結束時，手上沒有股票的最大累積利潤。

沒有股票會有兩種情況：

  • 今天剛賣掉股票。
  • 今天沒動作（昨天沒買股票）。
  1. 找出轉移式

要使 $dp[i]$ 最大化，有兩種可能：

  1. 不賣股票
  2. 賣

不賣股票的話，狀態會從昨天維持到現在，所以是 $dp[i - 1]$ 。

賣的話，代表在之前的某一天 $j$ $(j < i)$ 買入了股票，並在今天 $i$ 賣出。

利潤計算為：(今天股價) - (第 j 天買入價) + (第 j 天買入前的基礎利潤)。

由於有 $1$ 天冷凍期，若在第 $j$ 天買入，則上一筆交易最晚結束在第 $j-2$ 天。

這樣 dp 轉移式就會是 $P[i] + \max_{0 \le j < i} (dp[j-2] - P[j])$ 。

由於要最大化，因此得到

可以發現每次都要窮舉 $j$ ，會造成 $O(n^2)$ ，非常的浪費時間，因此可用一個變數 $m$ 來隨時記錄歷史最佳的買入點，也就是記錄 $\max(dp[j-2] - P[j])$ 的值。

然後可以進一步寫成：

同時計算完 $dp[i]$ 後，要為明天更新 $m$。如果選在今天（第 $i$ 天）買入，則其價值為 $dp[i-2] - P[i]$：

  1. 定義初始狀態

$dp[0] = 0$：第 0 天（還沒開始）利潤為 0。

$dp[1] = 0$：第 1 天只能買不能賣，所以手上沒股票的利潤仍為 0。

$m$：在計算第 2 天以前，唯一的買入機會是第 1 天。第 1 天買入的價值 $= dp[-1] - P[1]$。 $dp[-1]=0$，則：

:::info
註：在這邊的 $dp[-1]$ 指的是第 0 天的前一天的狀態，就是 Day -1 的狀態。

因為題目有 1 天冷凍期的限制，如果決定在 Day 1 買入股票，根據轉移式，必須在 Day -1 就已經把之前的股票賣掉並結束掉交易，這樣 Day 0 才是冷凍期，Day 1 才能買。

而 $dp[-1]$ 代表開始交易前或完全沒有發生過任何交易的狀態，那利潤當然就是 0。
:::

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);

    int n;
    cin >> n;

    int p[n];
    for (int i = 0; i < n; ++i) cin >> p[i];

    long long dp[n + 1] = {0};

    long long m = -p[0];

    for (int i = 2; i <= n; ++i) {
        int curr = p[i-1];

        dp[i] = max(dp[i-1], curr + m);

        m = max(m, dp[i-2] - curr);
    }

    cout << dp[n] << '\n';

    return 0;
}

練習題

Frog 1

Problem Source：https://atcoder.jp/contests/dp/tasks/dp_a

  1. 定義狀態： $dp[i]$ 是青蛙到達第 $i$ 顆石頭時的最小成本。
  2. 找出轉移式：

青蛙只有兩種方式可以跳到石頭 $i$：

  • 從石頭 $i-1$ 跳過來，成本：到達石頭 $i-1$ 的最小成本 + 從 $i-1$ 跳到 $i$ 的石頭高度。
    • $dp[i-1] + |hi - h{i-1}|$
  • 從石頭 $i-2$ 跳過來，成本：到達石頭 $i-2$ 的最小成本 + 從 $i-2$ 跳到 $i$ 的石頭高度。
    • $dp[i-2] + |hi - h{i-2}|$

由於要找的是最小成本，因此得到轉移式：

轉移式適用於 $i \ge 3$ 的情況，如果 $i = 2$，因為沒有石頭 0，青蛙只能從石頭 1 跳過來。

  1. 定義初始狀態：$dp[1] = 0$

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    
    int n;
    cin >> n;
    
    int h[n + 1];
    for (int i = 1; i <= n; ++i) cin >> h[i];
    
    int dp[n + 1];
    dp[1] = 0;
    
    for (int i = 2; i <= n; ++i){
        int j1 = dp[i - 1] + abs(h[i] - h[i - 1]);
        if (i > 2){
            int j2 = dp[i - 2] + abs(h[i] - h[i - 2]);
            dp[i] = min(j1, j2);
        }
        else{
            dp[i] = j1;
        }
    }
    cout << dp[n];
}

Frog 2

Problem Source：https://atcoder.jp/contests/dp/tasks/dp_b

  1. 定義狀態：同上題，$dp[i]$ 是青蛙到達第 $i$ 顆石頭時的最小成本。
  2. 找出轉移式：

青蛙可從 $i-1, i-2, \dots, i-K$ 這些位置跳過來（前提是那些位置存在，即編號 $\ge 1$）。

因此，對於每個 $i$ 來說，需要檢查前 $K$ 個可能的起跳點，並取其中的最小值：

  1. 定義初始狀態：
    • $dp[1] = 0$
    • 剩下的可以取一個無限大的數字。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int INF = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    
    int h[n + 1];
    for (int i = 1; i <= n; ++i) cin >> h[i];
    
    int dp[n + 1];
    fill(dp, dp + n + 1, INF);
    dp[1] = 0;
    
    for (int i = 2; i <= n; ++i){
        for (int j = 1; j <= k; ++j){
            if (i - j >= 1){
                dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
            }
            else{
                break;
            }
        }
    }

    cout << dp[n];
}

Typical Stairs

Problem Source：https://atcoder.jp/contests/abc129/tasks/abc129_c

  1. 定義狀態： $dp[i]$ 為到第 $i$ 階樓梯的方法總數。
  2. 找出轉移式：

由於到第 i 階僅能依靠這兩種方式：

  • 從第 $i-1$ 階跨 1 步上來。
  • 從第 $i-2$ 階跨 2 步上來。

而得到的轉移式會是 $dp[i] = dp[i - 1] + dp[i - 2]$

但題目有「損壞的階梯」的限制，如果第 $i$ 階是壞掉的，無法踩上去，所以到達該階的方法數應為 0。

可以考慮兩種情況：

  • 如果第 $i$ 階是損壞的：
  • 如果第 $i$ 階是完好的：
  1. 定義初始狀態：$dp[0] = 1$

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

const int MOD = 1000000007;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    bool isBroken[n + 1];
    fill(isBroken, isBroken + n + 1, false);
    
    for (int i = 0; i < m; ++i){
        int a;
        cin >> a;
        isBroken[a] = true;
    }
    
    int dp[n + 1] = {0};
    
    dp[0] = 1;
    
    for (int i = 1; i <= n; ++i){
        if (isBroken[i]){
            dp[i] = 0;
            continue;
        }
        dp[i] = dp[i - 1];
        if (i >= 2){
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }
    }
    
    cout << dp[n];
}