【C++】競程筆記（多維 DP、LCS 最長共同子序列）

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

什麼是多維的 DP?

一開始入門 DP 所寫的全都是一維的 DP，例如在爬樓梯問題， dp[i]dp[i] 就表示成到達第 ii 階的方法數。

而當中只有一個變數，叫做 ii ，故稱為一維 DP。

多維的 DP 就是有多個變數的 DP，一個變數不足以清楚描述當前的子問題，需要兩個或更多的變數來鎖定狀態。

例如：

  • 走迷宮需要 x,yx, y 座標兩個變數來表示 dp[x][y]dp[x][y]
  • LCS（Longest Common Subsequence：最長共同子序列）需要字串 A 的位置 ii 和字串 B 的位置 jj 表示 dp[i][j]dp[i][j]
  • 背包問題：需要物品編號 ii 和剩餘重量 ww 表示 dp[i][w]dp[i][w]

Vacation

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

狀態定義：不能只紀錄 dp[i]dp[i] 代表第 ii 天的最大快樂值，因為要知道第 ii 天到底做了什麼活動，才能決定第 i+1i+1 天不能做什麼。

這邊可以應用多維 DP 的想法，擠在同一個 DP 裡面：

  • dp[i][0]dp[i][0] ：第 ii 天選擇活動 A 的最大總快樂值。
  • dp[i][1]dp[i][1] ：第 ii 天選擇活動 B 的最大總快樂值。
  • dp[i][2]dp[i][2] ：第 ii 天選擇活動 C 的最大總快樂值。

但也可以分成三個 dp 去宣告做狀態定義：

  • dpa[i]dpa[i]
  • dpb[i]dpb[i]
  • dpc[i]dpc[i]

用哪一個都沒差，最後寫法還是一樣。

轉移式定義：

  • dp[i][0]=a[i]+max⁡(dp[i−1][1],dp[i−1][2])dp[i][0] = a[i] + \max(dp[i-1][1], dp[i-1][2])
  • dp[i][1]=b[i]+max⁡(dp[i−1][0],dp[i−1][2])dp[i][1] = b[i] + \max(dp[i-1][0], dp[i-1][2])
  • dp[i][2]=c[i]+max⁡(dp[i−1][0],dp[i−1][1])dp[i][2] = c[i] + \max(dp[i-1][0], dp[i-1][1])

如果今天選 A，那昨天一定只能選 B 或 C（取昨天兩者中較大的一個）。

如果今天選 B，那昨天一定只能選 A 或 C。

如果今天選 C，那昨天一定只能選 A 或 B。

題目限制兩天不能做一樣的事情。

base case 初始狀態：

  • dp[0][0]=a[0]dp[0][0] = a[0]
  • dp[0][1]=b[0]dp[0][1] = b[0]
  • dp[0][2]=c[0]dp[0][2] = c[0]

在 NTUCPC Guide 中採取的是後者：

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

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    const int MAXN = 100005;
    int a[MAXN], b[MAXN], c[MAXN];
    int dpa[MAXN], dpb[MAXN], dpc[MAXN];
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i] >> b[i] >> c[i];
    }
    for (int i = 1; i <= n; ++i){
        dpa[i] = max(dpb[i - 1] + a[i], dpc[i - 1] + a[i]);
        dpb[i] = max(dpa[i - 1] + b[i], dpc[i - 1] + b[i]);
        dpc[i] = max(dpa[i - 1] + c[i], dpb[i - 1] + c[i]);
    }
    // 三個及以上變數取最大值用 {}
    cout << max({dpa[n], dpb[n], dpc[n]}) << '\n';
}

用多維 DP 的好處是，可以將這些繁瑣的步驟用迴圈去跑，不用一個一個寫轉移式。（code from NTUCPC Guide）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
 
const int MAXN = 100005;
 
int happiness[MAXN][3];
int dp[MAXN][3];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) 
        for (int j = 0; j < 3; ++j)
            cin >> happiness[i][j];
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 3; ++j)
            for (int k = 0; k < 3; ++k)
                if (j != k)
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + happiness[i][j]);
    }
    cout << *max_element(dp[n], dp[n] + 3) << "\n";
}

股票買賣 V

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

先前的做法是先定義好狀態跟轉移式，之後再透過整理轉移式得到 O(n)O(n) 解。

但學會多維 DP 後，可直接得到 O(n)O(n) 解，省去整理轉移式的麻煩。

狀態定義：

  • dp[i][0]dp[i][0] ：有股票。可能是今天剛買的，或者之前買了還沒賣。
  • dp[i][1]dp[i][1] ：剛賣出股票。今天賣出，導致明天進入冷凍期。
  • dp[i][2]dp[i][2] ：沒股票且非冷凍期。可能是昨天就沒股票，或者昨天是冷凍期今天解凍了，是隨時可以買入的狀態。

轉移式定義：

  • 持有股票的狀態， dp[i][0]dp[i][0]
    • 狀況 A：昨天就持有股票，今天不賣 →dp[i−1][0]\rightarrow dp[i-1][0]
    • 狀況 B：昨天沒股票也沒被冷凍，今天買入 →dp[i−1][2]−prices[i]\rightarrow dp[i-1][2] - prices[i]

dp[i][0]=max⁡(dp[i−1][0],dp[i−1][2]−prices[i])dp[i][0] = \max(dp[i-1][0], dp[i-1][2] - prices[i])

  • 剛賣出股票 dp[i][1]dp[i][1]
    • 昨天持有股票，今天賣掉。

dp[i][1]=dp[i−1][0]+prices[i]dp[i][1] = dp[i-1][0] + prices[i]

  • 沒股票且非冷凍期 dp[i][2]dp[i][2]：
    • 狀況 A：昨天沒買股票，繼續觀望 →dp[i−1][2]\rightarrow dp[i-1][2]
    • 狀況 B：昨天剛賣出，今天強制休息（冷凍期） →dp[i−1][1]\rightarrow dp[i-1][1]

dp[i][2]=max⁡(dp[i−1][2],dp[i−1][1])dp[i][2] = \max(dp[i-1][2], dp[i-1][1])

初始狀態定義，第 0 天（第一筆資料）：

  • dp[0][0]dp[0][0]（持有）：只能是當天買入，利潤為負 →−prices[0]\rightarrow -prices[0]
  • dp[0][1]dp[0][1]（剛賣）：第一天不可能賣出，設為極小值或 0（邏輯上不可能發生） →0\rightarrow 0
  • dp[0][2]dp[0][2]（沒股票、冷凍期）：第一天什麼都不做 →0\rightarrow 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
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int N;
    cin >> N;

    int prices[N + 5];
    for (int i = 0; i < N; ++i) cin >> prices[i];

    int dp[N + 5][3];

    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    dp[0][2] = 0;

    for (int i = 1; i < N; ++i) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]);

        dp[i][1] = dp[i-1][0] + prices[i];

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


    cout << max(dp[N-1][1], dp[N-1][2]) << '\n';

    return 0;
}

組合數

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

這題是關於組合數 C(n,m)C(n, m) 的計算。

組合公式：$$C(n, m) = \frac{n!}{m!(n-m)!}$$

計算階乘是非常慢的，而且題目的查詢量 qq 有到 10410^4 ，因此改用二維 DP 結合帕斯卡三角形來做： $$C^n_m = C^{n-1}m + C^{n-1}{m-1}$$

狀態定義：定義 dp[i][j]dp[i][j] 為從 ii 個元素中選出 jj 個的方法數，也就是 C(i,j)C(i, j)。

轉移式定義：

根據帕斯卡三角形的性質「從 ii 個元素選 jj 個」的方法數等於以下兩者之和：

  • 不包含第 ii 個元素：前 i−1i-1 個裡面選 jj 個 →dp[i−1][j]\rightarrow dp[i-1][j]
  • 包含第 ii 個元素：前 i−1i-1 個裡面選 j−1j-1 個 →dp[i−1][j−1]\rightarrow dp[i-1][j-1]

因此得到完整的轉移式：$$dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) \pmod{10^9 + 7}$$

初始狀態定義：選 0 個，從任意 ii 個元素中選 0 個，只有一種方法（都不選）。$$dp[i][0] = 1$$

由於是有多筆查詢，而且 N 數量較少，所以改成直接建表，之後每筆查詢都能用 O(1)O(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
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1005;

int dp[MAXN][MAXN];

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    for (int i = 0; i <= 1000; i++) {
        dp[i][0] = 1; // C(n, 0) = 1
        
        for (int j = 1; j <= i; j++) {
            // 帕斯卡三角形公式 C(n, m) = C(n-1, m-1) + C(n-1, m)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
        }
    }

    int q;
    cin >> q;
    while (q--){
      int n, m;
      cin >> n >> m;
      cout << dp[n][m] << '\n';
    }
    
    return 0;
}

最長共同子序列（Longest Common Subsequence, LCS）

LCS 是非常經典且重要的演算法問題，特別在字串處理、生物資訊學（DNA 比對）以及版本控制系統（Git 的 diff 功能）等中都有廣泛應用。

那這也是很經典的 DP 例題，非學不可。

子字串 vs. 子序列

  • 子字串（Substring）：必須是連續的。
    • 例如：“ABCDE” 的子字串是 “BCD”。
  • 子序列（Subsequence）：不一定要連續，但先後順序不能改變。
    • 例如：“ABCDE” 的子序列可以是 “ACE” 或 “BD”。

LCS 定義

給定兩個序列（字串）S1S1 和 S2S2，找出一個最長的序列，同時出現在 S1S1 和 S2S2 中。

假設有兩個字串 A、B：

  • 字串 A："ABCBDAB"
  • 字串 B："BDCABA"

它們的 LCS 是 "BCBA"。

LCS 可能不只一個，如 "BDAB" 也是長度為 4 的共同子序列，但通常求的都是「最長的長度」。

818 . Longest Common Subsequence

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

  1. 狀態定義： dp[i][j]dp[i][j] 代表「字串 A 的前 ii 個字元」與「字串 B 的前 jj 個字元」 的 LCS 長度。

當 i=0i=0 時，代表字串 A 取了 0 個字元（空字串）。

當 i=n,j=mi=n, j=m 時， dp[n][m]dp[n][m] 即為兩完整字串的 LCS 長度。

  1. 轉移式定義
    • 字元相同：如果 AA 的第 ii 個字元等於 BB 的第 jj 個字元（A[i−1]=B[j−1]A[i-1] = B[j-1]），該字元必屬於 LCS 的一部分。 $$dp[i][j] = dp[i-1][j-1] + 1$$
    • 字元不同： A[i−1]≠B[j−1]A[i-1] \neq B[j-1] ，兩字元無法同時成為 LCS 的結尾。 $$dp[i][j] = \max(dp[i-1][j], \quad dp[i][j-1])$$

至於字元不同的情況，那 A[i]A[i] 和 B[j]B[j] 不可能同時被選入當作結尾，此時有兩種選擇：

  • A[i]A[i] 沒用，把它丟掉 →\rightarrow 問題變成找 「AA 的前 i−1i-1 個」跟「BB 的前 jj 個」。
  • B[j]B[j] 沒用，把它丟掉 →\rightarrow 問題變成找 「AA 的前 ii 個」跟「BB 的前 j−1j-1 個」。

在這兩種選擇中取兩者中的最大值，因為要求 LCS。

  1. 初始狀態定義 $$dp[0][j] = 0, \quad \text{for } 0 \le j \le m$$ $$dp[i][0] = 0, \quad \text{for } 0 \le i \le n$$

範例程式碼：

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 <string>
#include <algorithm>

using namespace std;

const int MAXN = 5005;
int dp[MAXN][MAXN];

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

    string A, B;
    cin >> A >> B;
    int n = A.length();
    int m = B.length();

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (A[i - 1] == B[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

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

    return 0;
}

更高維度的 DP：a252. Another LCS

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

從二維的 DP 變成三維 DP。

解法跟二維 DP 的 LCS 差不多，需注意 A[i−1]=B[j−1]=C[k−1]A[i - 1] = B[j - 1] = C[k - 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>
#include <string>
#include <algorithm>

using namespace std;

const int MAXN = 105;

int dp[MAXN][MAXN][MAXN];

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

    string A, B, C;
    cin >> A >> B >> C;
    int n = A.length();
    int m = B.length();
    int l = C.length();

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            for (int k = 1; k <= l; k++){
                if (A[i - 1] == B[j - 1] && B[j - 1] == C[k - 1]){
                    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                } else{
                    int maxVal = dp[i-1][j][k];
                    maxVal = max(maxVal, dp[i][j - 1][k]);
                    maxVal = max(maxVal, dp[i][j][k - 1]);
                    dp[i][j][k] = maxVal;
                }
            }
        }
    }

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

    return 0;
}