# 動態規劃 DP
## 簡介
動態規劃(dynamic programming) 英文簡稱 DP
他的目標在於將一個複雜的大問題，分割成多個小問題進行求解，並將答案進行合併從而得到問題的答案
而他的重點也不像分治是對問題進行分而「治」之
而是對這些分割並求得解的答案進「紀錄」，並可以用於重複利用
簡單來說就是 ==**以空間換時間**==
## 時間的比較
既然我們提到了 DP 是用空間換取時間
那我們就來實際比較看看用遞迴和動態規劃的時間差別
### 費式數列算效能的差距
#### 對單個數值重複取值
我們可以明顯發現動態規劃和遞迴的時間差距十分大
動態規劃把值記錄下來，所以時間永遠都一樣，而時間複雜度只有$O(1)$
但遞迴每次都需要重複執行，所以時間複雜度為$O(2^N)$
:::spoiler 範例程式碼-遞迴
```cpp=
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1e9+7;
int cnt=0;
int fib(int n){
cnt++;
if(n==0 or n==1) return 1;
return fib(n-1)+fib(n-2)%mod;
}
int main(){
clock_t start,finish;
start=clock();
for(int i=0; i<10000; i++){
fib(30);
}
finish=clock();
cout << finish-start<< endl;
}
```
:::
:::spoiler 範例程式碼-動態規劃
```cpp=
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9+7;
const int a=30;
int arr[a+1];
int main(){
clock_t start,finish;
start=clock();
arr[0]=1;
arr[1]=1;
for(int i=2; i<50; i++){
arr[i]=arr[i-1]+arr[i-2]%mod;
}
for(int i=0; i<10000; i++){
int d=arr[a];
}
finish=clock();
cout<<finish-start<<endl;
}
```
:::
有興趣也可以親自去實驗看看
## 經典題目
### 費氏數列
以最基礎的費氏數列做為開端
因為他的每一項的值皆固定，所以我們只需將她每個值先存取起來，需要用到時再取出即可，不用重複計算
時間複雜度$O(1)$
$dp$ 式: $dp[i]=dp[i-1]+dp[i-2]$ % $1000000007$
因為題目要求的數字可能會很大，所以記得取餘數
題目[a814 簡單的費事數列](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a814)
:::spoiler AC程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define endl '\n' ;
#define mod 1000000007
#define maxn 1000000+1
long long arr[maxn];
long long fib( long long num )
{
long long dp[maxn];
dp[0] = 1;
dp[1] = 1;
if(arr[num]==0){
arr[1]=1;
arr[0]=1;
for(int i = 2; i < maxn; ++i){
dp[i] = (dp[i-1] + dp[i-2])%mod;
arr[i]=dp[i];
}
return arr[num];
}
else{
return arr[num];
}
}
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
int n,q;
for(int i=0; i<maxn+1; i++){
arr[i]=0;
}
long long num = 0;
cin >>n>>q;
cin.get();
while(cin >> num){
cout << fib(num) << endl;
}
return 0;
}
```
:::
### 捷徑問題
題目[a048: 排列組合好討厭!!](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a048)
題目要求為從左下走到右上最近的方式有多?
排列組合告訴我們最快的方法為**角柱法**就是用加的。
也就是用**DP**
定義：`dp[i][j]` 是走到目前格子的捷徑數目
那麼，我們可以知道，這一個格字可以由下方及左方行經
然後最初的格字只有一種方法可以走到
所以我們可以列出轉移式：
$dp[i][j] = \begin{cases}
0 & i == 0\ ||\ j == 0\ ||\ (i, j)\ is\ wall\\
1\\
dp[i - 1][j] + dp[i][j - 1]\ \ & i > 0\ \&\&\ j > 0
\end{cases}$
再根據題目要求輸出 **dp[a-1][b-1]** 即為答案
:::spoiler AC程式碼
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1000;
unsigned int arr[N][N];
int main(){
for(int i=0; i<N; i++){
arr[i][0]=1;
arr[0][i]=1;
}
for(int i=1; i<N; i++){
for(int j=1; j<N; j++){
arr[i][j]=arr[i-1][j]+arr[i][j-1];
}
}
int n;
while(cin>>n){
for(int i=1; i<=n; i++){
int a,b;
cin>>a>>b;
a--;b--;
cout<<"Cas3 "<<i<<" : "<<arr[a][b];
if(arr[a][b]==1) cout<<" step"<<endl;
else cout<<" steps"<<endl;
}
}
}
```
:::
### 最長共同子序列 (Longest Common Subsequence)
英文簡稱 **LCS**
* 子序列為可以對字串進行切割，但不能交換位置
我們可以先用一個 **經典範例** 來觀察看看子序列
**frankie** 和 **friend**的**LCS**為多少
首先我們會發先這題的共同點為字母，所以我們要找字母相同的`LCS`
而在
$franki$ 和 $fr$ `LCS` 長度為 $2$
$frank$ 和 $fri$ `LCS` 長度為 $2$
此時若跑到兩邊皆為 $i$，那此時的 `LCS` 應該改成 $fri$，長度為 $3$
可以看出來最後一個字母若相同必為跑到的這個字母，而且長度$\,+\,1$
反過來說，若不同，則和 `LCS` 的變化無關，因此我們只要將兩種狀態所得到的 `LCS`
選擇其中最大者作為現在狀態的 `LCS` 即可
所以我們可以寫出遞迴式
定義現在的位置為原字串第 $i$ 格，另一字串的第 $j$ 格
當然，沒有任何字母時 `LCS` 長度為 $0$，即 `LCS` 為空
$lcs[i][j] = \begin{cases}
max(lcs[i - 1][j], lcs[i][j - 1]) & s1[i]\ != s2[j] \\
lcs[i - 1][j - 1] + 1 & s1[i] == s2[j]
\end{cases}$
題目[a627: Step by Step (Easy Version)](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a627)
:::spoiler 參考程式碼 **NA 59%**
```cpp=
#include <iostream>
using namespace std;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
string s1, s2;
while (cin >> s1 >> s2) {
s1 = "a" + s1; // 使用內建 operator + 來合併兩個字串
s2 = "b" + s2; // 為了變成 1-base，方便程式操作
int lcs[s1.length()][s2.length()] = {};
for (int i = 1; i < s1.length(); i++)
for (int j = 1; j < s2.length(); j++)
if (s1[i] == s2[j])
lcs[i][j] = lcs[i - 1][j - 1] + 1;
else
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
cout << lcs[s1.length() - 1][s2.length() - 1] << '\n';
}
return 0;
}
```
:::
如果依照上面的遞迴式寫，會發現得到$RE$
這是因為我們超過了記憶體的上限，這時候就需要想辦法減少空間複雜度，也就是**滾動DP**
:::warning
**滾動DP的目的是降低DP所帶來的空間複雜度**
:::
而我們會發現這題只需要他的**上、左上、左和現在這格就行了**
所以我們可以使用兩個傳統陣列來做這題
:::spoiler AC程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,n;
cin>>t;
while(t--){
cin>>n;
int arr[n],dp[n];
for(int i=0; i<n; i++){
cin>>arr[i];
dp[i]=1;
}
for(int r=1; r<n; r++){
for(int l=0; l<r; l++){
if( arr[r] >= arr[l] )
dp[r]=max(dp[r], dp[l]+1);
}
}
int mx=-1;
for(auto &i : dp) mx = max(mx, i);
cout<<mx<<endl;
}
}
```
:::
## 進階題型
### 0/1背包問題
他是最基礎的背包問題，其中每個物品可以只能選擇放或不放，請在有限空間內找出最大的價值
而在程式中我們稱 $0=false$也就是不放 $1=true$也就是放
所以我們統稱這類型的題目為 **0/1背包問題**
先觀察題型，我們可以得知，當能放時，只要考慮放進去之後有沒有更好
若沒有更好，不更新狀態；若更好，則更新
那我們先將每一列當作一個物品的狀態
定義：`dp[i+1][j]` 為考慮第 $i$ 個物品時，容量為 $j$ 的背包，能夠拿取的最大價值 (最優解)
則 `dp[i][j]` 代表了不放入這個物品的狀況
而放入物品則由「剛好能放入的情形」加上這個物品的價值得到
因為若限制容量愈小，愈不可能出現最優解 (很直觀)
因此只要去存取「剛好」能放入的情形即可
因此可以初步寫出轉移式：
```
dp[i+1][j] = max(dp[i][j], dp[i][j – vol[i]] + val[i]);
```
但當容量不足以放下時，我們應該也要可以從上一個推得
故在容量小於物品大小時，選擇不放，直接由上面敘述的「不放入」進行實作
因此我們推得最終轉移式：
\begin{cases}
dp[i+1][j] = max(dp[i][j], dp[i][j – w[i]] + v[i])，v[i] >= j \\
dp[i+1][j] = dp[i][j]，v[i] < j
\end{cases}
:::success
這樣的解法時間複雜度為 $O(NW)$，$N$ 是物品數量，$W$ 是背包容量
空間複雜度同為 $O(NW)$
:::
但當我們把code丟出去之後，會發現只拿到**NA60%**
:::spoiler NA60%
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,c;
while(cin>>n>>c){ //n==東西 c==體積
int w[n+1],v[n+1];//w==價值 v==體積
int dp[n+1][c+1];
int a,b;
w[0]=0;
v[0]=0;
for(int i=0; i<=n; i++){
for(int j=0; j<=c; j++){
dp[i][j]=0;
}
}
for(int i=1; i<=n; i++){
cin>>a>>b;
w[i]=a;
v[i]=b;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=c; j++){
if(j<v[i]){
dp[i][j]=dp[i-1][j];
}
else{
dp[i][j]=max(dp[i-1][j],w[i]+dp[i-1][j-v[i]]);
}
}
}
cout<<dp[n][c]<<endl;
}
}
:::
這是因為我們超過了最大的陣列空間，也就是所謂的**RE**
所以我們應該要想辦法降低空間複雜度
而我們可以發現他每次判斷時只會用到這個物品和上個物品的最大價值，所以我們可以利用基偶去做優化
把空間複雜度壓到$O(2N)$
:::spoiler AC程式碼
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
int w[1001],v[1000001];//w==價值 v==體積
int dp[2][1000001];
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int n,c;
while(cin>>n>>c){ //n==東西 c==體積
int a,b;
w[0]=0;
v[0]=0;
for(int i=0; i<2; i++){
for(int j=0; j<=c; j++){
dp[i][j]=0;
}
}
for(int i=1; i<=n; i++){
cin>>a>>b;
w[i]=a;
v[i]=b;
}
int e=1,o=0;
for(int i=1; i<=n; i++){
if(i%2==0){
e=0;
o=1;
}
else{
e=1;
o=0;
}
for(int j=1; j<=c; j++){
if(j<v[i]){
dp[e][j]=dp[o][j];
}
else{
dp[e][j]=max(dp[o][j],w[i]+dp[o][j-v[i]]);
}
}
}
cout<<dp[e][c]<<endl;
}
}
```
:::
題目[a279: 校長的背包問題](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a279)
### 有限背包問題
他和**0/1背包**不一樣的地方是，他的每個物品不會只有一個，而是有$N$個
所以我們可以把它用二進為分割成一個一個擁有不同價值的物品，而剩下就照著**0/1背包**的方式實作
:::success
時間複雜度相較以上面兩者多了一點為 $O(NWlgX)$，$N$ 是物品數量，$W$ 是背包容量，$X$ 是最大物品個數
而這個做法不是最優，他可以進行 `DP convex hull (凸包) 優化`
將 $lgX$ 壓掉，不過這非常進階，比賽也很少卡這個 $lgX$
因為實作方式是 $0 / 1$ 背包，空間複雜度還是 $O(W)$
:::
題目[a330: 主任的背包問題](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a330)
:::spoiler AC程式碼
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
long long w[10001],v[10001];//w==價值 v==體積
long long dp[1000001];
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int n,c;
while(cin>>n>>c){ //n==東西 c==體積
int tmp=0;
for(int i=0; i<1000001; i++){
dp[i]=0;
}
for(int i=1; i<=n; i++){
int a,b,k;
cin>>a>>b>>k;
int s=1;
while(s<=k){
tmp++;
w[tmp]=a*s;
v[tmp]=b*s;
k-=s;
s*=2;
}
if(k>0){
tmp++;
w[tmp]=a*k;
v[tmp]=b*k;
}
}
n=tmp;
for(int i=1; i<=n; i++){
for(int j=c; j>=v[i]; j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[c]<<endl;
}
}
```
:::
### 無限背包問題
他和**0/1背包**不一樣的地方在於他每個物品都沒有限制個數
所以我們不能從前方窮舉到後方，而是從後方窮舉到前方
所以我們可以得到結論:
==無限背包和 $0 / 1$ 背包的實作差別就在於向後和向前窮舉容量==
:::success
時間複雜度同樣為 $O(NW)$，$N$ 是物品數量，$W$ 是背包容量
因為和 $0 / 1$ 背包差不多，空間複雜度也為 $O(W)$
:::
題目[a331: 復旦的背包問題](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a331)
:::spoiler AC程式碼
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
long long w[1001],v[1001];//w==價值 v==體積
long long dp[1000001];
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int n,c;
while(cin>>n>>c){ //n==東西 c==體積
int a,b;
w[0]=0;v[0]=0;
for(int i=0; i<=c; i++){
dp[i]=0;
}
for(int i=1; i<=n; i++){
cin>>a>>b;
v[i]=a;
w[i]=b;
}
for(int i=1; i<=n; i++){
for(int j=w[i]; j<=c; j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[c]<<endl;
}
}
```
:::
上面是三個經典的背包問題，如果有興趣可以寫寫看下面的變種背包題型
題目[a822: Benson 打排球](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a822)
Google Drive
Gist
Clipboard
Sign in with Wallet
