# 【C++】競程筆記（DP：狀態跟轉移）
[TOC]
題目範例參考：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）挑出最大的那個。
範例程式碼：
```cpp=
#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$ 條路徑所能獲得的最大總分。
第二個就是找出轉移式，根據前面的定義可以寫出 $$dp[i] = max(dp[i + 1] + P_i, dp[i + 2] + 2 \times P_i)$$
第三個則是定義初始狀態，若當 $i > n$ 時（超出路徑範圍），得分為 0，即 $dp[n+1] = 0, dp[n+2] = 0$。
這題採用由後往前推的方法會比較好做，如果用由前面往後推的話，可以剛好跑完第 $n$ 關結束，也可以在第 $n-1$ 關加速直接衝過終點（跑到虛擬的 $n+1$ 關），最後的答案會是 $max(dp[n], dp[n+1])$ ，要多檢查一步。
範例程式碼：
```cpp=
#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。
$$dp[i] = \max_{0 \le j < i} \{ dp[j] \} + 1$$
限制條件是：
- $S[j] \le S[i]$ （當前小組和非負）
- $dp[j] \neq -\infty$ （前 $j$ 個可以合法分組）
3. 初始狀態：就是 $dp[0] = 0$
範例程式碼：
```cpp=
#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$ 天結束時，手上沒有股票的最大累積利潤。
沒有股票會有兩種情況：
- 今天剛賣掉股票。
- 今天沒動作（昨天沒買股票）。
2. 找出轉移式
要使 $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])$ 。
由於要最大化，因此得到 $$dp[i] = max(dp[i - 1], 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] = \max(dp[i-1], P[i] + m)$$
同時計算完 $dp[i]$ 後，要為明天更新 $m$。如果選在今天（第 $i$ 天）買入，則其價值為 $dp[i-2] - P[i]$：$$m = \max(m, dp[i-2] - P[i])$$
3. 定義初始狀態
$dp[0] = 0$：第 0 天（還沒開始）利潤為 0。
$dp[1] = 0$：第 1 天只能買不能賣，所以手上沒股票的利潤仍為 0。
$m$：在計算第 2 天以前，唯一的買入機會是第 1 天。第 1 天買入的價值 $= dp[-1] - P[1]$。 $dp[-1]=0$，則：
$$m = -P[1]$$
:::info
註：在這邊的 $dp[-1]$ 指的是第 0 天的前一天的狀態，就是 Day -1 的狀態。
因為題目有 1 天冷凍期的限制，如果決定在 Day 1 買入股票，根據轉移式，必須在 Day -1 就已經把之前的股票賣掉並結束掉交易，這樣 Day 0 才是冷凍期，Day 1 才能買。
而 $dp[-1]$ 代表開始交易前或完全沒有發生過任何交易的狀態，那利潤當然就是 0。
:::
範例程式碼：
```cpp=
#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] + |h_i - h_{i-1}|$
- 從石頭 $i-2$ 跳過來，成本：到達石頭 $i-2$ 的最小成本 + 從 $i-2$ 跳到 $i$ 的石頭高度。
- $dp[i-2] + |h_i - h_{i-2}|$
由於要找的是最小成本，因此得到轉移式： $$dp[i] = \min(dp[i-1] + |h_i - h_{i-1}|, \quad dp[i-2] + |h_i - h_{i-2}|)$$
轉移式適用於 $i \ge 3$ 的情況，如果 $i = 2$，因為沒有石頭 0，青蛙只能從石頭 1 跳過來。
3. 定義初始狀態：$dp[1] = 0$
範例程式碼：
```cpp=
#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$ 個可能的起跳點，並取其中的最小值：$$dp[i] = \min_{1 \le j \le K, \ i-j \ge 1} \left( dp[i-j] + |h_i - h_{i-j}| \right)$$
3. 定義初始狀態：
- $dp[1] = 0$
- 剩下的可以取一個無限大的數字。
範例程式碼：
```cpp=
#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$ 階是損壞的：$$dp[i] = 0$$
- 如果第 $i$ 階是完好的：$$dp[i] = (dp[i-1] + dp[i-2]) \pmod{10^9 + 7}$$
3. 定義初始狀態：$dp[0] = 1$
範例程式碼：
```cpp=
#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];
}
```
Sign in with Wallet
Connect another wallet