## 動態規劃
### 2/23 社課
---
## 動態規劃
----
動態規劃（Dynamic Programming），簡稱DP，透過把原問題分解為相對簡單的子問題來求解，並且把已經算過的數字存起來，之後再碰到就可以直接用。
----
### 解題方法
* 問題拆解，找到問題之間的關聯
* 定義DP狀態
* 列出轉移式
* 初始化邊界條件
---
## 費氏數列
----
### [Zerojudge - 東東爬階梯](https://zerojudge.tw/ShowProblem?problemid=d212)
給定一個整數$0<n<100$，假設階梯有$n$階，每次可以走一階或兩階，求有幾種走法
----
* 走到第$i$階可以由第$i-1$階走$1$階，也可以由第$i-2$階走$2$階
* 令$dp[i]$為走$i$階的方法數
* $dp[i]=dp[i-1]+dp[i-2]$
* $dp[0]=dp[1]=1$
* $ans=dp[n]$
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[100];
signed main()
{
int i,n;
dp[0]=dp[1]=1;
for(i=2;i<100;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
while(cin >> n)
{
cout << dp[n] << "\n";
}
}
```
----
### [CSES - Dice Combinations](https://cses.fi/problemset/task/1633)
給定一個整數$1\le n\le 10^{6}$，可以骰六面骰子任意次數，求有多少種方法使得點數總和是$n$，順序交換算不同次
----
* 總和為$i$可以由原本總和$i-1$骰到$1$，由原本總和$i-2$骰到$2$，依此類推
* 令$dp[i]$為總和$i$點的方法數
* $dp[i]=\sum_{k=1}^{6}dp[i-k],i-k\ge 0$
* $dp[0]=1$
* $ans=dp[n]$
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
int dp[1000001];
signed main()
{
int n,i,j;
cin >> n;
dp[0]=1;
for(i=1;i<=n;i++)
{
for(j=max(0ll,i-6);j<=i-1;j++)
dp[i]=(dp[i]+dp[j])%MOD;
}
cout << dp[n] << "\n";
}
```
----
### [CSES - Dice Probability](https://cses.fi/problemset/task/1725)
給定整數$1\le n\le 100$，$1\le a,b\le 6n$，骰六面骰子$n$次，求點數總和介於$a$和$b$之間的機率
----
* 總和為$i$可以由原本總和$i-1$骰到$1$，其中骰到1的機率為$\frac{1}{6}$，依此類推
* 令$dp[i][j]$為骰了$i$次，總和$j$點的機率
* $dp[i][j]=\frac{1}{6}\sum_{k=1}^{6}dp[i-1][j-k],j-k\ge 0$
* $dp[0][0]=1$
* $ans=\sum_{k=a}^{b}dp[n][k]$
----
程式碼：
```cpp
#include <bits/stdc++.h>
using namespace std;
double dp[101][601];
int main()
{
int n,a,b,i,j,k;
double ans=0;
cin >> n >> a >> b;
dp[0][0]=1;
for(i=1;i<=n;i++)
{
for(j=0;j<=i*6;j++)
{
for(k=max(0,j-6);k<=j-1;k++)
dp[i][j]+=dp[i-1][k];
dp[i][j]/=6;
}
}
for(;a<=b;a++)
{
ans+=dp[n][a];
}
cout << fixed << setprecision(6) << ans << "\n";
}
```
---
## 前綴和
----
### [CSES - Static Range Sum Queries](https://cses.fi/problemset/task/1646)
給定一長度為$n$的陣列$x_1,x_2,\dots,x_n$，並有$q$次詢問，每次詢問求陣列$[a,b]$範圍內的和，$1\le n,q\le2\cdot 10^5$
* 一維前綴和
----
* 令$dp[i]$為前$i$項的前綴和
* $dp[i]=dp[i-1]+x_i$
* $dp[0]=0$
* $ans=dp[b]-dp[a-1]$
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[200001];
signed main()
{
int n,q,x,i,a,b;
cin >> n >> q;
for(i=1;i<=n;i++)
{
cin >> x;
dp[i]=dp[i-1]+x;
}
while(q--)
{
cin >> a >> b;
cout << dp[b]-dp[a-1] << "\n";
}
}
```
----
### [CSES - Forest Queries](https://cses.fi/problemset/task/1652)
給定一$n\times n$的二維陣列，每個位置是$0$或$1$，並有$q$次詢問，每次詢問求陣列$(y_1,x_1)\sim(y_2,x_2)$範圍內的和，$1\le n\le1000,1\le q\le2\cdot 10^5$
* 二維前綴和
----
* 令$dp[i][j]$為$(1,1)\sim(i,j)$範圍內的和
* $dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+c_{i,j}$
* $dp[0][0]=dp[0][1]=\dots=dp[0][n]=0$
* $dp[0]dp[0]=dp[1][0]=\dots=dp[n][0]=0$
* $ans=dp[y_2][x_2]-dp[y2][x1-1]-dp[y1-1][x2]+dp[y1-1][x1-1]$
----
預處理：
----
詢問：
----
程式碼
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1001][1001];
signed main()
{
int n,q,i,j,y1,x1,y2,x2;
char c;
cin >> n >> q;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin >> c;
if(c=='*')
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+1;
else
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
}
}
while(q--)
{
cin >> y1 >> x1 >> y2 >> x2;
cout << dp[y2][x2]-dp[y2][x1-1]-dp[y1-1][x2]+dp[y1-1][x1-1] << "\n";
}
}
```
---
## 最大子陣列
----
### [CSES - Maximum Subarray Sum](https://cses.fi/problemset/task/1643)
給定一個長度為$n$的陣列$x_1,x_2,\dots,x_n$，$1\le n\le 2\cdot 10^5$，求最大連續非空子陣列和
----
* 要有至少一個元素
* 令$dp[i]$為前$i$項的最大連續非空子陣列和
* $dp[i]=max(dp[i-1]+x_i,x_i)$
* $dp[0]=0$
* $ans=max(dp[1],dp[2],\dots,dp[n])$
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[200001];
signed main()
{
int n,x,ans=LONG_LONG_MIN,i;
cin >> n;
for(i=0;i<n;i++)
{
cin >> x;
dp[i]=max(dp[i-1]+x,x);
ans=max(ans,dp[i]);
}
cout << ans << "\n";
}
```
----
### [ZeroJudge - 投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
給定一個長度為$n$的陣列$x_1,x_2,\dots,x_n$，$1\le n\le 150000$，求最大連續子陣列和，其中可以跳過$k$個數字，$k\le 20$
----
* 可以不包含任何元素
* 令$dp[i][j]$為跳過$i$個數字，前$j$項的最大連續子陣列和
* $dp[0][0]=dp[1][0]=\dots=dp[k][0]=0$
* $dp[0][j]=max(dp[j-1]+x_j,0)$
* $dp[i][j]=max(dp[i-1][j-1],dp[i][j-1]+x_j)$
* $ans=max(dp[k][1],dp[k][2],\dots,dp[k][n])$
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int x[150001],dp[21][150001];
signed main()
{
int n,k,i,j;
cin >> n >> k;
for(j=1;j<=n;j++)
{
cin >> x[j];
dp[0][j]=max(dp[0][j-1]+x[j],0ll);
}
for(i=1;i<=k;i++)
{
for(j=1;j<=n;j++)
{
dp[i][j]=max(dp[i-1][j-1],dp[i][j-1]+x[j]);
}
}
cout << *max_element(dp[k]+1,dp[k]+n+1) << "\n";
}
```
---
## 背包問題
----
### [AtCoder - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)
有$N$種物品，每種物品有重量$w$與價值$v$
每個物品最多可以選一次，求選的物品重量不超過$W$的情況，價值總和最大是多少
* $0/1$背包問題，代表選或不選
----
* 令$dp[i][j]$為選前$i$個物品且重量$\le j$的最大價值
* $dp[i][j]=max(dp[i-1][j],dp[i-1][j-w_i]+v_i)$
* $dp[0][0]=dp[0][1]=\dots=dp[0][W]=0$
* $ans=dp[N][W]$
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[101][100001];
signed main()
{
int N,W,w,v,i,j;
cin >> N >> W;
for(i=1;i<=N;i++)
{
cin >> w >> v;
for(j=0;j<=W;j++)
{
dp[i][j]=max(dp[i-1][j],j-w>=0?dp[i-1][j-w]+v:0);
}
}
cout << dp[N][W] << "\n";
}
```
----
### [Luogu - 宝物筛选](https://www.luogu.com.cn/problem/P1776)
有$n$種物品，每種物品有重量$w$、價值$v$與數量$m$
每個物品最多可以選$m$次，求選的物品重量不超過$W$的情況，價值總和最大是多少
* 有限背包問題，每種物品有數量限制
----
* 把每一種物品拆成$m$個物品，用$0/1$背包解
* TLE
----
* 令$m=2^{p}-1+k$，其中$k$滿足$k\le2^{p}-1$，則物品可分成$2^{0},2^{1},\dots,2^{p-1},k$個
* 以上的數字可以湊出所有$\le m$的任何數字
* 每個數字為一堆，當成一個物品，用$0/1$背包解
----
* 證明：
* 1. 假設所需的數字$\le 2^{p}-1$，則這個數字可以表示為二進制的$p$位數字，考慮每一位可以是$0$或$1$，這個數字有$2^p$種排列方式，又數字最小值為每位都是$0$ $=0$，最大值為每位都是$1$ $=2^0\times\frac{2^p-1}{2-1}=2^p-1$，因此這$2^p$個數剛好對應到$0\sim2^p-1$
* 2. 假設所需的數$>2^{p}-1$，且最大值為$m$，這個數字$\le2^{p}-1+k$，由1.可知$2^{p}-1$內的數字都可以湊出來，因此$\ge k$且$\le2^{p}-1+k$的數字也可以湊出來，又$k\le2^{p}-1$，因此$> 2^{p}-1$且$\le2^{p}-1+k$的數字都可以被湊出來
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[40001];
signed main()
{
int n,W,v,w,m,i,j,tmp;
cin >> n >> W;
for(i=1;i<=n;i++)
{
cin >> v >> w >> m;
for(tmp=1;tmp<=m;tmp*=2)
{
m-=tmp;
for(j=W;j>=tmp*w;j--)
{
dp[j]=max(dp[j],dp[j-tmp*w]+tmp*v);
}
}
if(m)
{
for(j=W;j>=m*w;j--)
{
dp[j]=max(dp[j],dp[j-m*w]+m*v);
}
}
}
cout << dp[W] << "\n";
}
```
----
### [Luogu - 疯狂的采药](https://www.luogu.com.cn/problem/P1616)
有$m$種草藥，每種草藥有採收需要時間$a$與價值$b$
每種草藥可以無限制地採，求採收時間不超過$t$的情況，價值總和最大是多少
* 無限背包問題，物品沒有數量限制
----
* 令$dp[i]$為總時間$\le i$的最大價值
* $dp[i]=max(dp[i],dp[i-a_j]+b_j)$
* $dp[0]=0$
* $ans=dp[t]$
* 因為在任何時間都可以選任何草藥，所以每種草藥可以取無限次
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[10001],b[10001],dp[10000001];
signed main()
{
int t,m,i,j;
cin >> t >> m;
for(i=1;i<=m;i++)
cin >> a[i] >> b[i];
for(i=1;i<=t;i++)
{
for(j=1;j<=m;j++)
{
if(a[j]<=i)
dp[i]=max(dp[i],dp[i-a[j]]+b[j]);
}
}
cout << dp[t] << "\n";
}
```
---
## 硬幣問題
----
### [CSES - Minimizing Coins](https://cses.fi/problemset/task/1634)
給定$n$枚硬幣，價值$c_1,c_2,\dots,c_n$元，求最少要用幾個硬幣才能湊出$x$元，$1\le n\le 100,1\le x\le 10^6$
----
* 令$dp[j]$為湊出$j$元所需的最少硬幣數
* $dp[j]=min(dp[j],dp[j-c_i]+1)$
* $dp[0]=0$
* 先假設$dp[1]=dp[2]=\dots=dp[x]=INF$
* $ans=dp[x],dp[x]\not =INF$
* $ans$無解$,dp[x]=INF$
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define INF 0x3F3F3F3F
using namespace std;
int dp[1000001];
int main()
{
memset(dp,0x3F,sizeof(dp));
dp[0]=0;
int n,x,c,i,j;
cin >> n >> x;
for(i=1;i<=n;i++)
{
cin >> c;
for(j=c;j<=x;j++)
{
if(dp[j-c]!=INF)
dp[j]=min(dp[j],dp[j-c]+1);
}
}
if(dp[x]!=INF)
cout << dp[x] << "\n";
else
cout << -1 << "\n";
}
```
----
### [CSES - Coin Combinations I](https://cses.fi/problemset/task/1635)
給定$n$枚硬幣，價值$c_1,c_2,\dots,c_n$元，求湊出$x$元的方法數，不同順序算不同種，$1\le n\le 100,1\le x\le 10^6$
----
* 令$dp[i]$為湊出$i$元的方法數
* $dp[i]=dp[i]+dp[i-c_j]$
* $dp[0]=1$
* $ans=dp[x]$
* 在每個價錢都跑一次所有硬幣，所以不同順序也會被算進去
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
int c[101],dp[1000001];
signed main()
{
int n,x,i,j;
cin >> n >> x;
for(i=1;i<=n;i++)
cin >> c[i];
dp[0]=1;
for(i=1;i<=x;i++)
{
for(j=1;j<=n;j++)
{
if(i-c[j]>=0)
dp[i]=(dp[i]+dp[i-c[j]])%MOD;
}
}
cout << dp[x] << "\n";
}
```
----
### [CSES - Coin Combinations II](https://cses.fi/problemset/task/1636)
給定$n$枚硬幣，價值$c_1,c_2,\dots,c_n$元，求湊出$x$元的方法數，不同順序算同一種，$1\le n\le 100,1\le x\le 10^6$
----
* 令$dp[j]$為湊出$j$元的方法數
* $dp[j]=dp[j]+dp[j-c_j]$
* $dp[0]=1$
* $ans=dp[x]$
* 每個硬幣依序跑一次所有價錢，因此必定照著題目給的順序，同一種組合只會有一種排列
----
程式碼：
```cpp
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
int dp[1000001];
signed main()
{
int n,x,c,i,j;
cin >> n >> x;
dp[0]=1;
for(i=1;i<=n;i++)
{
cin >> c;
for(j=c;j<=x;j++)
dp[j]=(dp[j]+dp[j-c])%MOD;
}
cout << dp[x] << "\n";
}
```
{"title":"動態規劃","description":"動態規劃（Dynamic Programming），簡稱DP，透過把原問題分解為相對簡單的子問題來求解，並且把已經算過的數字存起來，之後再碰到就可以直接用。","contributors":"[{\"id\":\"3aeed4e7-1118-47e7-b0cc-18caea236427\",\"add\":11027,\"del\":854}]"}