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

[TOC]

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

## 823 . RGB

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

先定義三種顏色的代號以及對分數的貢獻（權重）：

- 紅色（$j=0$）：權重為 $-v_i$（題目要求扣掉紅色數字總和）。
- 綠色（$j=1$）：權重為 $+v_i$（題目要求加上綠色數字總和）。
- 藍色（$j=2$）：權重為 $0$（藍色不影響分數）。

最後再來定義狀態：定義 $dp[i][j]$ 為考慮到第 $i$ 個數字，且將第 $i$ 個數字塗上顏色 $j$ 時，目前所能獲得的最大價值。

- $i : 1 \le i \le N$
- $j : 0 \le j \le 2$ （分別代表紅、綠、藍）

求 DP 轉移式：

題目限制「相鄰的數字必須標上不同的顏色」，要計算第 $i$ 個數字塗某個顏色時，第 $i-1$ 個數字必須是另外兩種顏色之一，最終解答是從中選取較大者，再加上當前顏色的權重。

對第 $i$ 個數字 ($i > 1$)：

- 若第 $i$ 個塗紅色（$j=0$）：前一個必須是綠色或藍色。$$dp[i][0] = \max(dp[i-1][1], dp[i-1][2]) - v_i$$
- 若第 $i$ 個塗綠色（$j=1$）：前一個必須是紅色或藍色。$$dp[i][1] = \max(dp[i-1][0], dp[i-1][2]) + v_i$$
- 若第 $i$ 個塗藍色（$j=2$）：前一個必須是紅色或綠色。$$dp[i][2] = \max(dp[i-1][0], dp[i-1][1])$$

初始狀態定義：

當考慮序列中第 1 個數字（$i=1$）時，沒有前一個數字的限制，直接根據顏色計算價值。

- $dp[1][0] = -v_1$
- $dp[1][1] = +v_1$
- $dp[1][2] = 0$

最終答案：在塗完最後一個數字 $N$ 後，最後一個數字可能是紅、綠、藍任一種，取三者中的最大值即為答案：$$Answer = \max(dp[N][0], dp[N][1], dp[N][2])$$

時間複雜度： $O(N)$

空間複雜度： $O(N)$

記得 DP 陣列要是 long long，題目測資有點大。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;

long long dp[MAXN][3];

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N;
    cin >> N;
    int a[N + 5];
    for (int i = 1; i <= N; ++i) cin >> a[i];
    dp[1][0] = -a[1];
    dp[1][1] = a[1];
    dp[1][2] = 0;
    for (int i = 1; i <= N; ++i){
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) - a[i];
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + a[i];
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]);
    }
    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << '\n';
}

## Grid 1

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

1. 狀態定義：$dp[i][j]$ 為從起點 $(1, 1)$ 走到座標 $(i, j)$ 的路徑總數。

- $i$（row），範圍 $1 \sim H$。
- $j$（column），範圍 $1 \sim W$。

2. 轉移式定義：

題目要求只能「向右」或「向下」移動。

要到達 $(i, j)$，只可能從上方 $(i-1, j)$ 或左方 $(i, j-1)$ 走過來。

對於每格 $(i, j)$，判斷規則如下：

- $(i, j)$ 是障礙物（`#`）：無法到達該格，路徑數為 0。$$dp[i][j] = 0$$
- $(i, j)$ 是空地（`.`）：路徑數等於「從上方來的路徑數」加上「從左方來的路徑數」。$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$

3. 初始狀態定義： $dp[1][1] = 1$ ，因為一開始就在 $(1, 1)$，算 1 種方法（停在原地）。

需要注意的是，當跑雙層迴圈，i == 1 且 j == 1 的情況要被跳過，否則後續計算會錯誤，結果會是 0。

另外在讀取 m 的字元時，當 j = W，會讀到字串結尾 `\0`，透過 j - 1 可以避開。

或是可以在輸入的時候做 padding（填充），就可以直接寫 `m[i][j]`：

for (int i = 1; i <= H; ++i) {
    string temp;
    cin >> temp;
    m[i] = " " + temp; // 手動加一個空白在前面
}

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int H, W;
    cin >> H >> W;
    vector <string> m(H + 1);
    for (int i = 1; i <= H; ++i) cin >> m[i];
    vector <vector <long long>> dp(H + 1, vector<long long>(W + 1, 0));
    dp[1][1] = 1;
    for (int i = 1; i <= H; ++i){
        for (int j = 1; j <= W; ++j){
            if (i == 1 && j == 1) continue;
            if (m[i][j - 1] == '#'){
                dp[i][j] = 0;
            }
            else{
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            }
        }
    }
    cout << dp[H][W] << '\n';
}

## P2386 放蘋果

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

1. 狀態定義： $dp[i][j]$ 是將 $i$ 顆蘋果放入 $j$ 個盤子的方法數。

2. 轉移式定義：
- 至少一個盤子為空：既然盤子是相同的，空哪個都沒差。可先將一個盤子移走，不用它。將 $i$ 個蘋果放入 $j-1$ 個盤子。 $$dp[i][j - 1]$$
- 所有盤子都有放蘋果（無空盤）：
- 每個盤子至少要有一個蘋果。
- 可先在每個盤子上各放 $1$ 個蘋果（消耗掉 $j$ 個蘋果）。
- 剩下的蘋果數量為 $i - j$ 個。
- 問題轉化為「將剩下的 $i-j$ 個蘋果，放入 $j$ 個盤子（可隨意放）」。$$dp[i-j][j], i \ge j$$

最終得到 $$dp[i][j] = dp[i][j-1] + dp[i-j][j]$$

當 $i < j$ 時，因為不可能每個盤子都放蘋果，第二項為 0，即 $dp[i][j] = dp[i][j-1]$

3. 初始狀態定義：
- 沒有蘋果（$i=0$）：$$dp[0][j] = 1$$
- 只有 1 個盤子（$j=1$）：$$dp[i][1] = 1$$

範例程式碼：

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--){
        int m, n;
        cin >> m >> n;
        
        int dp[15][15] = {0};
        
        for (int j = 0; j <= n; ++j) dp[0][j] = 1;
        
        for (int i = 0; i <= m; ++i) dp[i][1] = 1;
        
        for (int i = 1; i <= m; ++i){
            for (int j = 1; j <= n; ++j){
                if (i < j){
                    dp[i][j] = dp[i][j - 1];
                }
                else{
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
        }
        cout << dp[m][n] << '\n';
    }
}

## N 箱 M 球

Problem Source：https://tioj.ck.tp.edu.tw/problems/1291

1. 狀態定義：$dp[i][j]$ 為將 $i$ 個不同的球，放入 $j$ 個相同的箱子，且沒有空箱的方法數。
- $i$ 代表當前處理到的球數（$1 \le i \le m$）
- $j$ 代表當前使用的箱子數（$1 \le j \le n$）
2. 轉移式定義：
- 考慮第 $i$ 顆球放入時的情況，此時已用 $j$ 個箱子，第 $i$ 顆球有兩種選擇：
1. 自己獨佔一個新箱子：代表前 $i-1$ 顆球已佔用了 $j-1$ 個箱子，第 $i$ 顆球放入第 $j$ 個箱子。方法數為：$$dp[i-1][j-1]$$
2. 放入已經有球的箱子中：代表前 $i-1$ 顆球已佔用了 $j$ 個箱子，第 $i$ 顆球可以放入這 $j$ 個箱子中的任一個。因為這 $j$ 個箱子裡面已有不同的球了，所以這 $j$ 個箱子被視為不同的箱子。方法數為：$$j \times dp[i-1][j]$$

最終得到：$$dp[i][j] = (dp[i-1][j-1] + j \times dp[i-1][j]) \pmod{1000000}$$

3. 初始狀態定義：
- $dp[0][0] = 1$：0 個球放入 0 個箱子，視為一種方法（空集合）。

4. 最終答案：$$ans = \sum_{k=1}^{n} dp[m][k] \pmod{1000000}$$

因為題目這邊要求的是使用 1 個箱子到使用 $n$ 個箱子的所有情況總和。

範例程式碼：

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 205;

const int MOD = 1000000;

long long dp[MAXN][MAXN];

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    dp[0][0] = 1;
    for (int i = 1; i < MAXN; ++i){
        for (int j = 1; j <= i; ++j){
            dp[i][j] = (dp[i - 1][j - 1] + j * dp[i - 1][j]) % MOD;
        }
    }
    int n, m;
    while (cin >> n >> m && (n != 0 || m != 0)){
        long long ans = 0;
        for (int k = 1; k <= n && k <= m; ++k) ans = (ans + dp[m][k]) % MOD;
        cout << ans << '\n';
    }
}

## 幸運表格

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

1. 狀態定義：$dp[i][j]$ 為從座標 $(i, j)$ 出發，依照規則走到離開表格為止，所能獲得的最大幸運指數總和。
2. 轉移式定義：為了讓總和最大，選「右」、「下」兩方向中值較大的那一個。
- 向右走：
- 如果右邊還有格子（$j+1 < M$），得到$$dp[i][j+1]$$
- 如果右邊是邊界（離開表格），得到$$0$$
- 向下走：
- 如果下面還有格子（$i+1 < N$），得到 $$dp[i+1][j]$$
- 如果下面就是邊界（離開表格），得到 $$0$$

最終得到：$$dp[i][j] = A[i][j] + \max(\text{向右獲利}, \text{向下獲利})$$

當中 $A[i][j]$ 是幸運表格的數字。

3. 初始狀態定義：最右下角的格子 $(N-1, M-1)$ 因為右邊和下面都是界外，所以 $dp[N-1][M-1] = A[N-1][M-1] + \max(0, 0)$。

在程式設計上，由於計算 $(i, j)$ 需要用到 $(i+1, j)$ 和 $(i, j+1)$ 的值，須由右下角往左上角計算。

範例程式碼：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = -1e9;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
  
    int n, m;
    cin >> n >> m;
    
    vector <vector<int>> a(n, vector<int>(m, 0));
    vector <vector<int>> dp(n, vector<int>(m, 0));
    
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j)
        cin >> a[i][j];
    
    int ans = INF;
    
    for (int i = n - 1; i >= 0; --i){
      for (int j = m - 1; j >= 0; --j){
        int right_gain = 0;
        if (j + 1 < m){
          right_gain = dp[i][j + 1];
        }
        
        int down_gain = 0;
        if (i + 1 < n){
          down_gain = dp[i + 1][j];
        }
        
        dp[i][j] = a[i][j] + max(right_gain, down_gain);
        
        if (dp[i][j] > ans){
          ans = dp[i][j];
        }
      }
    }
    
    cout << ans << '\n';
}

## APCS 2020/10 P3 勇者修煉

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

1. 狀態定義：

定義兩個輔助狀態陣列，及一個最終狀態陣列（假設目前處理到第 $i$ 列）：

- $L[j]$ ：表示到達位置 $(i, j)$，且最後一步是由上方 $(i-1, j)$ 或是左方 $(i, j-1)$ 走過來的最大經驗值。（向右掃描）
- $R[j]$ ：表示到達位置 $(i, j)$，且最後一步是由上方 $(i-1, j)$ 或是右方 $(i, j+1)$ 走過來的最大經驗值。（向左掃描）
- $dp[i][j]$：表示從起點到達 $(i, j)$ 的最終最大經驗值。

在同一列中，一條路徑不可能同時「先向左再向右」或「先向右再向左」，這樣會經過同一格兩次，所以到達 $(i, j)$ 的最佳路徑，必定是 $L[j]$ 和 $R[j]$ 兩者取其大。

2. 轉移式定義：

假設已算完第 $i-1$ 列的結果，記為 $prev\_dp$，現在要計算第 $i$ 列的值，該格的經驗值為 $cost[i][j]$。

對於第 $i$ 列的每一個位置 $j$：

- 向右掃描 $L[j]$ ：考慮從「上一列直接下來」比較好，還是從「這一列的左邊走過來」比較好。$$L[j] = cost[i][j] + \max(prev\_dp[j], L[j-1])$$
- 邊界條件：若是第一欄 $j=0$，則只能從上面下來，不能從左邊來。
- 向左掃描 $R[j]$ ：考慮從「上一列直接下來」比較好，還是從「這一列的右邊走過來」比較好。$$R[j] = cost[i][j] + \max(prev\_dp[j], R[j+1])$$
- 邊界條件：若是最後一欄 $j=m-1$，則只能從上面下來，不能從右邊來。
- 最後 $dp[i][j]$ 取兩者為最大值：$$dp[i][j] = \max(L[j], R[j])$$

3. 初始狀態定義：所有上面要用的陣列大小為 m，都設 0。

這邊採用的是滾動 DP 的方式解題，能節省空間。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> grid[i][j];

    vector<ll> prev_dp(m, 0);
    
    vector<ll> L(m), R(m);

    vector<ll> dp(m);

    for (int i = 0; i < n; ++i) {
        // 向右掃描
        // L[j] = grid[i][j] + max(從上面來, 從左邊來)
        for (int j = 0; j < m; ++j) {
            ll from_up = prev_dp[j];
            ll from_left = (j == 0) ? -1e18 : L[j - 1];
            
            if (j == 0) L[j] = grid[i][j] + from_up;
            else L[j] = grid[i][j] + max(from_up, from_left);
        }
        // 向左掃描
        // R[j] = grid[i][j] + max(從上面來, 從右邊來)
        for (int j = m - 1; j >= 0; --j) {
            ll from_up = prev_dp[j];
            ll from_right = (j == m - 1) ? -1e18 : R[j + 1];

            if (j == m - 1) R[j] = grid[i][j] + from_up;
            else R[j] = grid[i][j] + max(from_up, from_right);
        }

        for (int j = 0; j < m; ++j) dp[j] = max(L[j], R[j]);
        
        prev_dp = dp;
    }

    ll ans = -2e18;
    for (ll val : prev_dp) 
      if (val > ans) ans = val;

    cout << ans << '\n';

    return 0;
}

## 連鎖店 (Chains)

Problem Source：https://tioj.ck.tp.edu.tw/problems/1938

題目中所謂每家都要開在前一家的東北方，意思就是$N$ 個點的 $X$ 與 $Y$ 座標都必須是嚴格遞增。

1. 狀態定義：$dp[k][y]$ 為在考慮當前的 $X$ 座標時，已選取了 $k$ 家連鎖店，且第 $k$ 家店位於 $Y$ 座標為 $y$ 的位置時，所有連鎖店累積的最大顧客數總和。
2. 轉移式定義：

當遍歷到第 $x$ 列時，嘗試在此列放置第 $k$ 家店。

假設要在 $(x, y)$ 放置第 $k$ 家店，根據題目要求，第 $k-1$ 家店必須位於 $(x', y')$，其中 $x' < x$ 且 $y' < y$。

因為是由 $x = 0$ 到 $M-1$ 依序計算，當處理到 $x$ 時，$dp$ 表中儲存的正是 $x' < x$ 的最佳解，因此只要注意 $y$ 的限制（$y' < y$）即可。

可得轉移式：$$dp[k][y] = \max(dp[k][y], \quad \text{profit}(k, x, y) + \max_{0 \le y' < y} \{ dp[k-1][y'] \})$$

- $\text{profit}(k, x, y) = (a \cdot (k-1) + b \cdot x + c \cdot y) \mod d$
- $\max_{0 \le y' < y} \{ dp[k-1][y'] \}$ 代表在前幾列中，選了 $k-1$ 家店且 $Y$ 座標小於目前 $y$ 的最大值。

為了避免用到同一列 $x$ 更新過的資料（$x$ 不能相同），在實作時，內層迴圈計算 $k$ 時應由大到小（$N$ 到 $1$），或者使用暫存變數，確保所讀取的 $dp[k-1]$ 是來自之前的 $x$ 列。

3. 初始狀態定義：所有 $dp[k][y]$ 初始化為一個極小值。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main(){
  ios::sync_with_stdio(false), cin.tie(nullptr);
  
  int M, N;
  ll a, b, c, d;
  cin >> M >> N >> a >> b >> c >> d;
  
  vector <vector<ll>> dp(N + 1, vector<ll>(M + 1, -1));
  
  for (int x = 0; x < M; ++x){
    for (int k = N; k >= 1; --k){
      ll max_prev = -1;
      
      for (int y = 0; y < M; ++y){
        ll profit = (a * (k - 1) + b * x + c * y) % d;
        
        // 如果是第 1 家店
        if (k == 1) dp[k][y] = max(dp[k][y], profit);
        // 如果是第 2 家以上的店，需要看前一家店 (k-1) 的最大值
        else if (max_prev != -1) dp[k][y] = max(dp[k][y], max_prev + profit);
        
        if (k > 1) max_prev = max(max_prev, dp[k - 1][y]);
      }
    }
  }
  
  ll ans = 0;
  for (int y = 0; y < M; ++y)
      if (dp[N][y] != -1)
          ans = max(ans, dp[N][y]);
  cout << ans << '\n';
}

## Edit Distance

Problem Source：https://cses.fi/problemset/task/1639

1. 狀態定義：

令輸入的兩個字串分別為 $S$（長度 $n$）和 $T$（長度 $m$）。

$dp[i][j]$ 為將字串 $S$ 的前 $i$ 個字元轉換成字串 $T$ 的前 $j$ 個字元，所需的最少操作次數。

- $S[1 \dots i]$ 表示 $S$ 的前 $i$ 個字元（index 1 based）。
- $T[1 \dots j]$ 表示 $T$ 的前 $j$ 個字元。

2. 轉移式定義：

對於 $dp[i][j]$，考慮 $S$ 的第 $i$ 個字元（$S[i]$）和 $T$ 的第 $j$ 個字元（$T[j]$）的關係。

可從三個方向轉移，分別對應三種操作：

1. 插入：假設 $S[1 \dots i]$ 已轉成 $T[1 \dots j-1]$，只要在 $S$ 的尾端插入一個字元 $T[j]$ 即可變成 $T[1 \dots j]$。$$dp[i][j-1] + 1$$
2. 刪除：假設 $S[1 \dots i-1]$ 已轉成 $T[1 \dots j]$，只要把 $S$ 原本多出來的第 $i$ 個字元刪除。$$dp[i-1][j] + 1$$
3. 替換：
- 如果 $S[i] == T[j]$ ，則不需要任何操作，直接繼承 $dp[i-1][j-1]$ 的結果。$$dp[i-1][j-1]$$
- 如果 $S[i] \neq T[j]$ ，把 $S$ 的第 $i$ 個字元替換成 $T$ 的第 $j$ 個字元。$$dp[i-1][j-1] + 1$$

最後得到轉移式：$$dp[i][j] = \min \begin{cases}
dp[i][j-1] + 1 & \text{(插入)} \\
dp[i-1][j] + 1 & \text{(刪除)} \\
dp[i-1][j-1] + cost & \text{(替換)}
\end{cases}$$

其中 $cost$ 的定義為若 $S[i] == T[j]$ 則 $cost = 0$，否則 $cost = 1$。

3. 初始狀態定義
- $dp[i][0] = i$：將 $S$ 的前 $i$ 個字元轉換成空字串，需要刪除 $i$ 次。
- $dp[0][j] = j$：將空字串轉換成 $T$ 的前 $j$ 個字元，需要插入 $j$ 次。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false), cin.tie(nullptr);
  
  string s, t;
  cin >> s >> t;
  
  int n = s.length(), m = t.length();
  
  vector <vector <int>> dp(n + 1, vector<int>(m + 1));
  
  for (int i = 0; i <= n; ++i) dp[i][0] = i;
  for (int j = 0; j <= m; ++j) dp[0][j] = j;
  
  for (int i = 1; i <= n; ++i){
    for (int j = 1; j <= m; ++j){
      int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
      dp[i][j] = min({
        dp[i - 1][j] + 1,
        dp[i][j - 1] + 1,
        dp[i - 1][j - 1] + cost
      });
    }
  }
  
  cout << dp[n][m] << '\n';
}