# 第四章 :基礎動態規劃
動態規劃最重要的就是練習，而且練習動態規劃的CP值很高，因為很多大型考試大部分都有超過一題。
動態規劃簡稱 $DP$ $(Dynamic-Programing)$ ，也被稱為「記憶化遞迴」，它的核心想法就是$$不要重複計算，把之前算過的紀錄下來，以空間換取時間。$$
$DP$ 與分治的概念很像，都是把問題由小而大的計算，先把問題劃分成子問題再合併子問題的答案變成最後的答案，總共有3個步驟 :
> 1. 定義子問題。
> 2. 找到問題與子問題之間的關係。
> 3. 找到計算子問題的順序，來避免重複計算重複的。
## 例題 : 費氏數列
> 費氏數列第$0$項定義為$0$，第$1, 2$項都定義為$1$，求費氏數列的第$n$項$\bmod10^9+7$。
> $1 \le n \le 10^6$
如果我們以遞迴關係式表示:
> $$
> F_i =
> \begin{cases}
> 1 & \text{if } i=1 \text{ or } 2\\
> F_{i-1} + F_{i-2} & \text{otherwise}
> \end{cases}
> $$
換成程式就變成
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int f(int n) {
if(n<3) return 1;
return f(n-1)+f(n-2)%mod;
}
```
根據我們在遞迴上的，在 $n=5$ 時可以畫成下圖，可以發現它在 $n=3$ 時重複計算了，時間複雜度其實不是 $O(n)$，而是可怕的 $O(1.6^n)$，因此根據 $DP$ 的想法，我們可以把已經計算過的紀錄下來，就可以避免多餘的計算。
所以我們可以用陣列紀錄費氏數列的每一項，也就是「記憶化遞迴」的精隨，避免重複計算，程式碼如下。
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[1000010];
int f(int n) {
if(n<3) return 1;
if(dp[n]!=-1) return dp[n];
return dp[n]=(f(n-1)+f(n-2))%mod;
}
signed main() {
int n;
cin>>n;
for(int i=0;i<=n;i++) dp[i]=-1;
cout<<f(n);
}
```
## $Top-down$ && $Bottom-up$
這樣由上而下做 $DP$，計算到哪一項再去看是否計算過的方法又被稱為 $Top-down$ 的 $DP$ ，與之相對的便是 $Bottom-up$ 的 $DP$。
$Bottom-up$ 在中國被稱為「嚴格位置依賴」，也就是如果要計算 $DP$ 中的任何一項，它所需要的每一項都需要被計算過，像是如果要把上面的程式碼轉成 $Bottom-up$ 的 $DP$ 可以轉成下面的程式碼。
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[1000010];
signed main() {
int n;
cin>>n;
dp[1]=dp[2]=1;
for(int i=3;i<=n;i++) {
dp[i]=(dp[i-1]+dp[i-2])%mod;//確定都計算過了，根據遞迴式。
}
cout<<dp[n];
}
```
$9\sim 12$行的程式跟遞迴式幾乎一樣只是改成使用迴圈而不是遞迴，還有$n \sim 1$改成由$1\sim n$
### 實作比較
#### $Top-down$
* 找到遞迴式就可以直接實作。
* 通常使用遞迴，速度相對慢，而且要注意遞迴的深度。
#### $Bottom-up$
* 要確定所有問題計算前，它的子問題已經計算好了。
* 通常使用迴圈，速度相對快。
**通常使用$Bottom-up$**
## 名詞介紹
### 狀態
一個狀態就是用一些參數決定一個子問題，定狀態就是璇則子問題需要紀錄哪些參數。
### 轉移
轉移指的就是狀態與狀態間的關係，與遞迴的方向相反，由小問題貢獻到大問題
e.g 從 $dp_{i-2}$ 和 $dp_{i-1}$ 轉移到 $dp_i$。
### $xDyD$
$n$ 是資料量。
$xDyD$ 的意思就是總共有 $n^x$ 個狀態，每個狀態會需要 $n^y$ 個子狀態。
e.g 費氏數列 $f_i=f_{i-1}+f_{i-2}$，總共有 $n$ 個狀態，每個狀態需要 $2$ 個子狀態，所以就是 $1D0D$ ，一個 $xDyD$ 的 $DP$ 的時間複雜度是 $O(n^{x+y})$
## $Bottom-up$的實作
### pull
* 就是用「拉」的
去找每個狀態需要由哪些狀態轉移
e.g.
```cpp=
dp[1]=1, dp[2]=1;
for(int i=3;i<=n;i++) {
dp[i]=dp[i-1]+dp[i-2];
}
```
### push
* 就是用「推」的
去找每個狀態可以轉移到哪些狀態
e.g.
```cpp=
dp[1]=1, dp[2]=1;
for(int i=1;i<=n;i++) {
if(i==1) dp[i+1]+=dp[i];
else {
dp[i+1]+=dp[i];
dp[i+2]+=dp[i];
}
}
```
## 例題 [vacation](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a560)
[原題](https://atcoder.jp/contests/dp/tasks/dp_c)
>Kzzz巨砲今年當上國手了，保送台大的他覺得暑假好無聊，於是他決定去游泳，跟朋友出門或為了之後的ICPC RK.1繼續刷題，暑假總共有$N$天，每天都不能做跟昨天一樣的事，每天做每一件事都有對應的快樂度$a_i，b_i，c_i$，請輸出在暑假結束他能獲得的最大快樂度。
$1 \le N \le 10^5$
我們可以發現如果第$i$天選擇要游泳那第$i-1$天就不能游泳，也就是第$i-1$天只能刷題或跟朋友出門所以我們可以定義
> $x_i$ 為第 $i$ 天游泳所能獲得的最大快樂度，$x_1=a_1$。
> $y_i$ 為第 $i$ 天跟朋友出門所能獲得的最大快樂度，$y_1=b_1$。
> $z_i$ 為第 $i$ 天刷題所能獲得的最大快樂度，$z_1=c_1$。
這題的遞迴式就可以列成這樣 :
> $x_i=\max(y_{i-1}, z_{i-1})+a_i$
> $y_i=\max(x_{i-1}, z_{i-1})+b_i$
> $z_i=\max(x_{i-1}, y_{i-1})+c_i$
:::spoiler AC-CODE
```cpp=
#include<bits/stdc++.h>
using namespace std;
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n;
cin>>n;
vector<vector<int>> dp(3, vector<int>(100010, 0));
cin>>dp[0][1]>>dp[1][1]>>dp[2][1];
for(int i=2;i<=n;i++) {
cin>>dp[0][i]>>dp[1][i]>>dp[2][i];
dp[0][i]+=max(dp[1][i-1], dp[2][i-1]); //不能由自己這項轉移
dp[1][i]+=max(dp[0][i-1], dp[2][i-1]); //不能由自己這項轉移
dp[2][i]+=max(dp[0][i-1], dp[1][i-1]); //不能由自己這項轉移
}
cout<<max(dp[0][n], max(dp[1][n], dp[2][n])); //最後還要看是選哪個比較好
}
```
:::
## 常見的$DP$題目
### 求方法數
題目通常會給你一些限制，問你到第$n$項的方法有幾種，跟機率類似。
### 找最佳解
給你一些限制，問你在滿足這些限制的情況最多可以獲得多少分數。
## 例題 [atcoder DP contest H](https://atcoder.jp/contests/dp/tasks/dp_h)
> 有一個由 $H$ 行和 $W$ 列組成的網格。我們用 $(i, j)$ 表示第 $i$ 行（從上往下數）和第 $j$ 列（從左往右數）的方格。
對於每個 $i$ 和 $j$ $（1\le i\le H, 1 \le j\le W）$，方格 $(i, j)$ 由一個字元 $a_{i,j}$ 描述。如果 $a_{i,j}$ 是 `.`，則方格 $(i, j)$ 是空方格；如果 $a_{i,j}$ 是 `#`，則方格 $(i, j)$ 是牆壁方格。保證方格 $(1,1)$ 和 $(H,W)$ 都是空方格。
太郎將從方格 $(1,1)$ 開始，通過不斷向右或向下移動至相鄰的空方格，最終到達方格 $(H,W)$。
請找出從方格 $(1,1)$ 到方格 $(H,W)$ 的所有可能路徑數量。由於答案可能非常大，請以 $\bmod(10^9 + 7)$ 後輸出結果。
> $1\le W, H \le 1000$
> $a_{i, j}=$ `.` 或 `#`
> 
我們可以定義 $DP_{i, j}$ 是走到第 $i$ 行第 $j$ 列的方法數$\bmod 10^9+7$，而且 $DP_{1, 1}=1$，因為是從這格出發，由於走到第 $i$ 行第 $j$ 列之後只能往右或往下走，也就是說 $DP_{i, j}$ 應該要從它左邊和上面的格子轉移，因為只有這兩格可以走到第 $i$ 行第 $j$ 列，所以可以推出轉移式是
> $DP_{1, 1}$=1
> $DP_{0, 1\sim W}=0，DP_{1\sim H, 0}=0$ 因為根本到不了。
> $DP_{i, j}=(DP_{i-1, j}+DP_{i, j-1}) \bmod 10^9+7$
但是如果$a_{i,j}$ 是 `#` 那這格根本到不了所以不能用 $DP_{i, j}$ 來轉移。完整的轉移式應該要是這樣
> $DP_{1, 1}$=1
> $DP_{0, 1\sim W}=0，DP_{1\sim H, 0}=0$ 因為根本到不了。
> $if a_{i,j} \not=$ # $DP_{i, j}=(DP_{i-1, j}+DP_{i, j-1}) \bmod 10^9+7$
> $else$ $DP_{i, j}=0$
:::spoiler AC-CODE
```cpp=
#include<bits/stdc++.h>
using namespace std;
signed main() {
int n, m, mod=1e9+7;
cin>>n>>m;
vector<vector<int>> dp(1010, vector<int> (1010, 0)); //一開始先初始化為0
vector<vector<char>> adj(1010, vector<char> (1010, ' '));
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
cin>>adj[i][j];
}
}
dp[1][1]=1;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(adj[i][j]=='.') dp[i][j]+=(dp[i][j-1]+dp[i-1][j])%mod; //可以走才轉移
}
}
cout<<dp[n][m];
}
```
:::
這題是 $2D0D$ 的 $DP$，因為總共有 $n^2$ 個狀態，每個狀態需要兩個子狀態來轉移，時間複雜度是 $O(n^2)$。
## 例題 LIS(最長遞增子序列)
> 有一個陣列 $a[1], a[2], a[3], ...a[N-1], a[N]$，選擇一個他的子序列，子序列需要滿足除了第一項外，每一項都必須大於前項，求最長的子序列長度。
> * 子序列定義
>
> 子序列是選擇原陣列的一些元素，在不改變選擇的元素的相對位置的情況所形成的序列。
> * 限制
>
> $1 \le N \le 2000$
>
> e.g. `4 7 6` 是`4 8 7 6 3`的子序列但`4 3 6`不是。
> 
如果把狀態定為 $DP_i$ 為到第 $i$ 項所能得到的最長子序列長度，感覺是對的但仔細想想又許多問題，可以發現 $DP_i$ 不一定會包含 $a_i$，但到 $DP_j$ 的時候，需要保證用來轉移狀態的 LIS 的最後一項必須小於 $a_j$，可是根據狀態的定義，我們無法確定用來轉移的 LIS 所選的最後一項是甚麼，所以我們無法透過這個狀態來做轉移。
那應該怎麼轉移呢 ?
:::spoiler 真的想不到再打開
### 把狀態定為 $DP_i$ 為，必須選擇 $a_i$ 當LIS的最後一項，而且到第 $i$ 項所能得到的最長子序列長度。
轉移到 $DP_j$ 的時候，可以由滿足 $i<j$ 且 $a_i<a_j$ 的任意一項 $DP_i$ 轉移，非常顯然一定是由 LIS 長度最長的 $DP_i$ 轉移
:::
::: spoiler AC-CODE
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int a[2010], dp[2010];
for(int i=1;i<=n;i++) {
dp[i]=1;
cin>>a[i];
}
int ans=1;
for(int i=2;i<=n;i++) {
for(int j=1;j<i;j++) {
if(a[i]>a[j]) {
dp[i]=max(dp[i], dp[j]+1);
ans=max(ans, dp[i]);
}
}
}
cout<<ans;
}
```
:::
這題是 $1D1D$ 的 $DP$ 因為總共有 $N$ 個狀態，每個狀態最多可能由 $N-1$ 個狀態來轉移，時間複雜度是 $O(n^2)$，這題可以優化到 $O(n \log n)$ 但這並不再這一章節的內容，如果有興趣的可以想看看。
## 例題 [LCS](https://atcoder.jp/contests/dp/tasks/dp_f)
> 給定字串 $s$ 和 $t$，找出它們的一個最長共同子序列。
> * 注意事項
>
>字串 $x$ 的子序列是通過從 $x$ 中移除零個或多個字元，並按原順序連接剩餘字元得到的字串。
>* 限制條件
>
>$s$ 和 $t$ 是僅由小寫英文字母組成的字串。
>$1 \leq |s|, |t| \leq 3000$。
>
>範例 : abcde abdff $\rightarrow$ LCS長度 : 3
很直覺的想法是 $dp_{i, j}$ 是 $s$ 的前 $i$ 個字元和 $t$ 的前 $j$ 個字元的 LCS長度。
但是如果 $s_i==t_j$ 那 LCS 長度應該要 +1，但是不知道該怎麼轉移。
如果 $s_i==t_j\ \text{AND } s_i==t_{j+1}$ ，LCS 的長度很明顯不能 +2 ，因為不能選擇 $s_i$ 兩次，所以如果 $s_i==t_j$ 那 $dp_{i, j}=dp_{i-1,j-1}+1$，這樣就可以保證不會選到重覆的。
如果 $s_i\not=t_j$，那 $dp_{i, j}=\max(dp_{i-1,j},dp_{i,j-1})$，因為 $dp_{i-1,j}$, $dp_{i,j-1}$ 根據定義是能轉移到的最長 LCS。
圖 from [Yui Huang 演算法學習筆記](https://yuihuang.com/dp-lcs/)
::: spoiler AC-CODE
```cpp=
#include<bits/stdc++.h>
using namespace std;
signed main() {
string s, t;
cin>>s>>t;
s=" "+s; //方便實作
t=" "+t; //方便實作
vector<vector<int>> dp(1010, vector<int>(1010, 0));
for(int i=1, l=s.size();i<l;i++) {
for(int j=1, len=t.size();j<len;j++) {
if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
}
}
cout<<dp[s.size()-1][t.size()-1];
}
```
:::
## 例題 [01背包](https://atcoder.jp/contests/dp/tasks/dp_d)
>給一個容量為 $M$ 的背包，還有 $N$ 個物品，第 $i$ 個物品的體積是 $a_i$ ，價值是 $b_i$，選擇一些物品放到背包中。求在總體積不超過背包容量，所能獲得的最大價值。
>
> * 限制條件
>
> $1 \le M \le 100$, $1 \le N \le 10^5$, $1 \le a_i, b_i \le 10^7$
### 暴力法
每一項都選或不選，再判斷總體積小於等於 $M$ 的最大價值，時間複雜度是 $O(2^N)$。
似乎就算剪枝也不太可行。
### DP
把狀態定義為 $DP_{i, W}$ 為只選擇前 $i$ 個物品且總體積小於等於 $W$ 所能獲得的最大價值。
如果選了第 $i$ 項那 $DP_{i, W}=DP_{i-1, W-a_i}+b_i$，如果不選第 $i$ 項那 $DP_{i, W}=DP_{i-1, W}$。
> $$
> DP_{i, w} = \max (DP_{i-1, W-a_i}+b_i, DP_{i, W}=DP_{i-1, W})
> $$
時間複雜度是 $O(MN)$。
* 實作
> 初始值是 0（不選任何東西）。
> 當 $w<a_i$ 時不能選第 𝑖 個物品。
:::spoiler AC-CODE
```cpp=
#include<bits/stdc++.h>
using namespace std;
// 可以不用開long long 因為100*10^7<2^32-1
signed main() {
int m, n; //m是容量, n是個數
cin>>n>>m;
vector<vector<int>> dp(110, vector<int>(10010, 0));
vector<int> a(n+1, 0), b(n+1, 0);
for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
for(int i=1;i<=n;i++) {
for(int j=0;j<=m;j++) {
if(j>=a[i]) {
dp[i][j]=max(dp[i-1][j], dp[i-1][j-a[i]]+b[i]);
}
else dp[i][j]=dp[i-1][j];
}
}
}
```
:::
其實背包問題還有無限背包還有有限背包，但筆者想多介紹一些不同思路的 $DP$，如果有興趣的可以自己上網找看看。
## 例題 旅行推銷員問題
>有 $N$ 棟房子，編號是 $0 \sim N-1$，房子 $i$ 和房子 $j$ 的距離是 $a[i][j]$，有一個推銷員要從房子 $0$ 出發，經過每間房子恰好一次再回到房子 $0$，請問他最短要走多遠?
>
> * 限制條件
>
> $2 \le N \le 17$, $0 \le a[i][j] \le 10^7$, $a[i][j]=a[j][i]$, $a[i][i]=a[i][i]$
### 枚舉法
排列 $0 \sim N-1$ 的所有可能，時間複雜度是 $O(N!)$，$17! \approx 3.5 \times 10^{14}$。
顯然不符合所求。
### DP
$DP_{i,[vis_{N-1}][vis_{N-2}][vis_{N-3}]...[vis_0]}$ 為目前在 $i$，$vis_j$ 是 $0 \text{ or } 1$，表示是否去過 $j$。
* 實作
>實作中，帶著一個18維的陣列轉移似乎有點太難了，所以要使用狀態壓縮。
>可以發現，因為只要記錄每個房子是否去過，所以要用二進位用一個`int`表達。
### 狀態壓縮
$$DP_{i,[vis_{N-1}][vis_{N-2}][vis_{N-3}]...[vis_0]}\rightarrow DP_{i, [vis_{N-1}vis_{N-2}vis_{N-3}...vis_0]}$$
e.g.
$$DP_{4, [1][0][1][0]} \rightarrow DP_{4, [{(1010)}_2]}$$
#### 位元運算
設已經走過的二進位集合為 $S={(1010)_2}$，$S$ 代表已經去過了第1間和第3間。
> $S \&(1<<j)$
(即判斷 $S$ 在二進制下從右數來第 $j+1$ 位是否為1)
> 用於檢查點 $j$ 是否在集合內。
> $\text{if }S \&(1<<J)==1$，代表點 $J$ 已經去過。
> $\text{else}$ 點 $J$ 沒有去過。
>e.g.
>$S=$<font color="#ff0000">$1010$</font>
>$1<<3$ $=$ <font color="#ff0000">$1$</font>$000$
>$S\&1<<3=1$
>$S-(1<<3)=0010 \rightarrow可以用減法把點3移除集合$
> $(1<<N)-1$ 就是去過所有點的集合。
:::spoiler AC-CODE
可能需要理解一下
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
signed main() {
int n, ans=1e9;
vector<vector<int>> a(17, vector<int>(17, 0)), dp(131072, vector<int>(17, INF));
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
cin>>a[i][j];
}
}
dp[1][0]=0; //從2^0出發，目前在第0間，距離設定為0。
for(int i=0;i<(1<<n);i++) { //枚舉所有可能的集合。
for(int j=0;j<n;j++) { //枚舉目前可能在哪一間。
if(i&(1<<j)) { //要點 j 有在 目前去過的集合中。
for(int k=0;k<n;k++) {
if((i&(1<<k))&&j!=k) { //可以枚舉上一間房子去哪裡，計算最短距離。
dp[i][j]=min(dp[i][j], dp[i-(1<<j)][k]+a[j][k]);
}
}
}
}
}
for(int i=1;i<n;i++) ans=min(ans, dp[(1<<n)-1][i]+a[i][0]); //枚舉所有可能的答案(最後在哪一間房子的總距離+那一間房子到點0的距離)
cout<<ans;
}
:::
時間複雜度由 $O(N!)$ 壓縮到 $O(N^22^N)$
## 例題 [$\text{Slimes}$](https://atcoder.jp/contests/dp/tasks/dp_n)
> 有 $N$ 個史萊姆排成一排，第 $i$ 隻史萊姆的大小是 $a[i]$ 。每次挑選兩隻相鄰的史萊姆結合在一起，大小變成兩隻史萊姆的大小相加，而花費也是兩隻史萊姆的大小相加，其他史萊姆的相對順序不變，經過 $N-1$ 次結合，所有的史萊姆會被合在一起，求最小的花費。
> * 限制條件
>
> $1 \le N \le 400, 1\le a[i] \le 10^9$
> e.g.
> `1|2|3` $\rightarrow$ `1|5` $\rightarrow$ `6` $cost=2+3+1+5=11$
>`1|2|3` $\rightarrow$ `3|3` $\rightarrow$ `6` $cost=1+2+3+3=9$
我們可以觀察到在任何時候「史萊姆一定是由一個連續的區段所組成，而且其大小為這個區間的和。」以及「如果要使用區間 $[L, R]$ 合成史萊姆。一定是由區間 $[L, K]$ 和區間 $[K+1, R]$ 組成。」
所以可以把子問題定義成「把陣列的子區間合成成一個最大史萊姆的最小花費。」
### DP
定義$DP_{L, R}$為把第 $L$ 隻到第 $R$ 隻的史萊姆都合成的最小總花費。
$$
DP_{L, R}=\\
\begin{cases}
0 \text{ if L=R}\\
DP_{L, K}+DP_{K+1, R}+\sum_{i=L}^Ra[i] \text{ otherwise}
\end{cases}
$$
* 計算$\sum_{i=L}^Ra[i]$
> 使用前綴和$b[i]=b[i-1]+a[i]$。$\sum_{i=L}^Ra[i]=b[R]-b[L-1]$ 可以 $O(1)$ 計算區間和。
* 實作
實作上需要注意如果由 $1\sim N$ 枚舉左右界進行轉移是不行的，因為計算 $dp_{L, R}$時 $dp_{L+1, R}$ 還沒計算。
:::spoiler AC-CODE
```cpp=
#include<bits/stdc++.h>
using nmaespace std;
#define int long long
const int INF=2e18;
vector<int> a(410, 0), b(410, 0);
vector<vector<int>> dp(410, vector<int>(410, INF))
signed main() {
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];
for(int i=1;i<n;i++) {
for(int j=1;j+i<=n;j++) {
int l=i, r=j+i;
for(int k=l;k<r;k++) {
dp[l][r]=min(dp[l][r], dp[l][k]+dp[k+1][r]+b[r]-b[l-1]);
}
}
}
cout<<dp[1][n];
}
```
:::
## 練習題
$DP$ 的練習方法真的只能多練，本章部分例題來自[Atcoder Educational DP Contest](https://atcoder.jp/contests/dp/tasks)。如果想要練習也可以來這看看。
也可以去 [$\text{Codeforces}$](https://codeforces.com/problemset?order=BY_RATING_ASC&tags=dp) 戳戳看一些 $DP$ 題目
Sign in with Wallet
Connect another wallet