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

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

什麼是多維的 DP?

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

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

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

例如：

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

Vacation

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

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

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

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

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

$dpa[i]$
$dpb[i]$
$dpc[i]$

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

轉移式定義：

$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][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][1] = b[0]$
$dp[0][2] = c[0]$

在 NTUCPC Guide 中採取的是後者：

#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）

#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)$ 解。

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

狀態定義：

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

轉移式定義：

持有股票的狀態， $dp[i][0]$
- 狀況 A：昨天就持有股票，今天不賣 $\rightarrow dp[i-1][0]$
- 狀況 B：昨天沒股票也沒被冷凍，今天買入 $\rightarrow 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][0] + prices[i]$$

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

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

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

$dp[0][0]$（持有）：只能是當天買入，利潤為負 $\rightarrow -prices[0]$
$dp[0][1]$（剛賣）：第一天不可能賣出，設為極小值或 0（邏輯上不可能發生） $\rightarrow 0$
$dp[0][2]$（沒股票、冷凍期）：第一天什麼都不做 $\rightarrow 0$

範例程式碼：

#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) = \frac{n!}{m!(n-m)!}$$

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

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

轉移式定義：

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

不包含第 $i$ 個元素：前 $i-1$ 個裡面選 $j$ 個 $\rightarrow dp[i-1][j]$
包含第 $i$ 個元素：前 $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 個，從任意 $i$ 個元素中選 0 個，只有一種方法（都不選）。$$dp[i][0] = 1$$

由於是有多筆查詢，而且 N 數量較少，所以改成直接建表，之後每筆查詢都能用 $O(1)$ 時間做到。

範例程式碼：

#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 定義

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

假設有兩個字串 A、B：

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

它們的 LCS 是 "BCBA"。

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

818 . Longest Common Subsequence

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

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

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

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

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

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

$A[i]$ 沒用，把它丟掉 $\rightarrow$ 問題變成找「$A$ 的前 $i-1$ 個」跟「$B$ 的前 $j$ 個」。
$B[j]$ 沒用，把它丟掉 $\rightarrow$ 問題變成找「$A$ 的前 $i$ 個」跟「$B$ 的前 $j-1$ 個」。

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

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

範例程式碼：

#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]$ 。

範例程式碼：

#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;
}