# 進階動態規劃
by: hush
---
## LIS
----
求一段長度為$n$的序列$a$的最長遞增子序列(Longest Increase Subsequence)的長度，這裡的子序列不一定要是連續的
----
- 定義狀態：
定義$dp[n+1]$，$dp[i]$代表以$a[i]$結尾的LIS長度
- 轉移式：$dp[i]=\max(dp[j])+1,\ j<i,\ a[j]<a[i]$
- 邊界條件(2選1)：
1.$\not\exists j<i,\ a[j]<a[i]$ 時 $dp[i]=1$
2.設$a[0]=-INF,\ dp[0]=0$(序列從1開始)
- 答案：$\max(dp[i])$
----
- 時間複雜度分析：
有$O(n)$個狀態，每個的轉移時間$O(n)$
總共需要$O(n^2)$，還可以更快
----
- 用Greedy的想法來看：
1.相同$dp$值我們只關心結尾最小的，所以我們可以開一個陣列存每個$dp$值的最小結尾
2.陣列值一定是遞增的（序列才能往後接），預設為INF
- 所以可以對陣列做二分搜！可以$O(log n)$內找到符合條件的最大$dp$值，並更新最小結尾
總時間$O(nlogn)$
----
實作上我們只需要開一個陣列維護每個$dp$值的最小結尾即可，預設為INF，最後答案就是最後一個不是INF的陣列索引
----
Code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
vector<int> dp(200005,1e18),a(200005);
signed main()
{
int n; cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
for (int i=0;i<n;i++)
{
int j=lower_bound(dp.begin(),dp.begin()+n,a[i])-dp.begin();
//非嚴格遞增改為upper_bound
dp[j]=a[i];
}
cout << lower_bound(dp.begin(),dp.begin()+n,1e18)-dp.begin() << endl;
}
```
----
- 練習題：
[APCS2101 P4 zj_f608](https://zerojudge.tw/Submissions?problemid=f608&account=rayho0319@gmail.com)
----
AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int> dp(200005,1e18);
vector<pii> a(200005);
signed main()
{
int n; cin >> n;
for (int i=0;i<n;i++) cin >> a[i].x >> a[i].y;
sort(a.begin(),a.begin()+n);
for (int i=0;i<n;i++)
{
int x=upper_bound(dp.begin(),dp.begin()+n,a[i].y)-dp.begin();
dp[x]=a[i].y;
}
cout << lower_bound(dp.begin(),dp.begin()+n,1e18)-dp.begin() << endl;
}
```
---
## LCS
----
求兩段長度為$n,\ m$的序列$A,\ B$的最長遞增子序列(Longest Common Subsequence)，這裡的子序列不一定要是連續的
----
- 定義狀態：
定義$dp[n+1][m+1]$，$dp[i][j]$代表考慮$A的前i項與B的前j項$的LCS長度
- 轉移式：
$\left\{
\begin{array}{l}
dp[i][j]=dp[i-1][j-1]+1,\ A[i]=B[j]\\
dp[i][j]=\max(dp[i-1][j],dp[i][j-1]),\ A[i]\not =B[j]
\end{array}
\right.$
----
- 邊界條件：
$dp[i][0]=dp[0][j]=0$
- 答案：$dp[n][m]$
----
- 時間複雜度分析：
有$O(nm)$個狀態，每個狀態轉移需要$O(1)$，總共是需要$O(nm)$時間
----
例題：[zj_a133](https://zerojudge.tw/ShowProblem?problemid=a133)
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
int a[105],b[105],n,m,cnt=1;
vector<vector<int>> dp(105,vector<int>(105));
signed main()
{
//colinorz;
while (cin >> n >> m)
{
if (n==0 && m==0) break;
for (int i=1;i<=n;i++) cin >> a[i];
for (int i=1;i<=m;i++) cin >> b[i];
for (int i=0;i<=n;i++)
{
for (int j=0;j<=m;j++)
{
if (i==0 || j==0) dp[i][j]=0;
else if (a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout << "Twin Towers #"<<cnt++<<"\nNumber of Tiles : " << dp[n][m] << endl;
}
}
```
----
練習題：[zj_c001](https://zerojudge.tw/ShowProblem?problemid=c001)
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
string s,t;
vector<vector<int>> dp(1005,vector<int>(1005));
signed main()
{
//colinorz;
while (cin >> s >> t)
{
int ss=s.size(),ts=t.size();
for (int i=0;i<=ss;i++)
{
for (int j=0;j<=ts;j++)
{
if (i==0 || j==0) dp[i][j]=0;
else if (s[i-1]==t[j-1]) dp[i][j]=max({dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]});
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout << dp[ss][ts] << endl;
}
}
```
----
另外的作法：
- LCS轉成LIS(歸約法)：
1.將$A$序列裡每個元素和它對應的index存到$M$(map)裡
2.構建一個$C$序列，依序將$B$序列的每個元素對應到$A$序列的index加入$C$序列的後方
3.$C$序列的LIS長度就是$A,\ B$的LCS長度
- p.s.: 若$A$有重複元素則將indexes存入vector，建構到$C$時以降冪順序建構
----
- 時間複雜度分析：
在重複數字較少時約為$O(n log n)$，不過最差情況會到$O(n^2logn^2)$，所以一般情況下較少用
$n大約是min(|A|,|B|)$
---
## 區間DP
----
- 例題：
[APCS2401_P4 合併成本](https://zerojudge.tw/ShowProblem?problemid=m934)
----
- 定義狀態：
定義$dp[n][n]$，$dp[i][j]代表合併i$~$j$的最小成本
- 轉移式：
$dp[l][r]=min(dp[l][i]+dp[i+1][r]+cost(l,i,r)),$
$i\in [l,r)$
- 邊界條件：
$dp[i][i]=0$
- 答案：
$dp[1][n]$
----
- 時間複雜度分析：
有$O(n^2)$個狀態，每次轉移需要$O(n)$的時間，總共是$O(n^3)$，可以更快但通常不需要
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
vector<int> pre(105,0);
vector<vector<int>> dp(105,vector<int>(105,-1));
inline int cost(int l,int i,int r)
{ return abs( (pre[r]-pre[i]) - (pre[i]-pre[l-1]) ); }
int mg(int l,int r)
{
if (l==r) return 0;
if (dp[l][r]!=-1) return dp[l][r];
int ans=1e18; //INF
for (int i=l;i<r;i++) //[l,r)
ans=min(ans,mg(l,i)+mg(i+1,r)+cost(l,i,r));
return dp[l][r]=ans;
}
signed main()
{
//colinorz;
int n; cin >> n;
for (int i=1;i<=n;i++) cin >> pre[i],pre[i]+=pre[i-1];
cout << mg(1,n) << endl;
}
```
----
- 練習題：
[atcoder_DP_N](https://atcoder.jp/contests/dp/tasks/dp_n)
----
AC code
```cpp=
#define int long long
#define itn int
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define endl '\n'
using namespace std;
vector<int> a(405),pre(405,0);
vector<vector<int>> dp(405,vector<int>(405,-1));
int slm(int l,int r) //[l,r]
{
if (l==r) return 0;
if (dp[l][r]!=-1) return dp[l][r];
int ans=1e18;
for (int i=l;i<r;i++) ans=min(ans,slm(l,i)+slm(i+1,r));
return dp[l][r]=ans+pre[r]-pre[l-1];
}
signed main()
{
//colinorz;
int n; cin >> n;
for (int i=1;i<=n;i++) cin >> a[i];
for (int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
cout << slm(1,n) << endl;
}
```
---
## 背包問題
----
- 0/1背包：一個物品只能取一次
- 無限背包：一個物品能取無限次
- 有限背包：一個物品能取有限次
----
### 0/1背包
有$N$種物品，每種物品的重量為$w[i]價值為v[i]$**且只有一個**，要放進一個耐重$W$的背包裡，求背包在不超重的情況最多可以裝到多少總價值
$1\le N\le 100$，$1\le W\le 10^5$
----
- 定義狀態：
定義$dp[N+1][W+1]$，$dp[i][j]$代表考慮到第$i$種物品且背包可承受重量為$j$的最大價值
- 轉移式：
$dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$
$,\ j\ge w[i]$
$dp[i][j]=dp[i-1][j]$，$j<w[i]$
----
- 邊界條件：
$dp[0][j]=0,\ j\le W$
- 答案：
$dp[N][W]$
----
- 時間複雜度分析：
有$O(NW)$個狀態，每次轉移需要$O(1)$的時間，總共是$O(NW)$
----
- 例題：
[atcoder_DP_D](https://atcoder.jp/contests/dp/tasks/dp_d)
----
AC code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define itn int
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
#define vi vector<int>
using namespace std;
vi w(105),v(105);
vector<vi> dp(105,vi(100005));
signed main()
{
int n,m; cin >> n >> m;
for (int i=1;i<=n;i++) cin >> w[i] >> v[i];
for (int i=0;i<=n;i++)
{
for (int j=0;j<=m;j++)
{
if (i==0||j==0) dp[i][j]=0;
else
{
if (j-w[i]<0) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
cout << dp[n][m] <<'\n';
}
```
----
- 練習題：
[atcoder_DP_E](https://atcoder.jp/contests/dp/tasks/dp_e)
----
定義狀態為$dp[i][j]$：
考慮到第$i$項且背包裝了$j$單位價值所需最小重量
----
AC code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define itn int
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
#define vi vector<int>
#define INF numeric_limits<int>::max()
using namespace std;
vi w(105),v(105);
vi dp(100005);
signed main()
{
itn n,m,ans=0; cin >> n >> m;
for (int i=1;i<=n;i++) cin >> w[i] >> v[i];
int vsum=0; for (int i=1;i<=n;i++) vsum+=v[i];
for (int i=0;i<=n;i++)
{
for (int j=vsum;j>=0;j--)
{
if (i==0&&j==0) dp[j]=0;
else if (i==0) dp[j]=-1;
else if (j-v[i]<0 || dp[j-v[i]]==-1) continue;
else if (dp[j]==-1) dp[j]=dp[j-v[i]]+w[i];
else dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}
for (int i=0;i<=vsum;i++)
if (dp[i]>=0 && dp[i]<=m) ans=i;
cout << ans <<'\n';
}
```
----
### 無限背包
有$N$種物品，每種物品的重量為$w[i]價值為v[i]$**且有無限個**，要放進一個耐重$W$的背包裡，求背包在不超重的情況最多可以裝到多少總價值
$1\le N\le 100$，$1\le W\le 10^5$
----
- 定義狀態：
定義$dp[N+1][W+1]$，$dp[i][j]$代表考慮到第$i$種物品且背包可承受重量為$j$的最大價值
- 轉移式：
$dp[i][j]=\max(dp[i-1][j],dp[i][j-w[i]]+v[i])$
$,\ j\ge w[i]$
$dp[i][j]=dp[i-1][j]$，$j<w[i]$
----
- 邊界條件：
$dp[0][j]=0,\ j\le W$
- 答案：
$dp[N][W]$
----
- 時間複雜度分析：
有$O(NW)$個狀態，每次轉移需要$O(1)$的時間，總共是$O(NW)$
----
code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define itn int
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
#define vi vector<int>
using namespace std;
vi w(105),v(105);
vector<vi> dp(105,vi(100005));
signed main()
{
int n,m; cin >> n >> m;
for (int i=1;i<=n;i++) cin >> w[i] >> v[i];
for (int i=0;i<=n;i++)
{
for (int j=0;j<=m;j++)
{
if (i==0||j==0) dp[i][j]=0;
else
{
if (j-w[i]<0) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
cout << dp[n][m] <<'\n';
}
```
----
### 有限背包
有$N$種物品，每種物品的重量為$w[i]價值為v[i]$且有$k[i]$個，要放進一個耐重$W$的背包裡，求背包在不超重的情況最多可以裝到多少總價值
----
- 定義狀態：
定義$dp[N+1][W+1]$，$dp[i][j]$代表考慮到第$i$種物品且背包可承受重量為$j$的最大價值
- 轉移式：
$dp[i][j]=\max(dp[i-1][j],dp[i][j-t\cdot w[i]]+$
$t\cdot v[i]),\ j\ge w[i],\ t\le k[i]$
$dp[i][j]=dp[i-1][j],\ j<w[i]$
- 邊界條件：
$dp[0][j]=0,\ j\le W$
----
- 時間複雜度分析：
有$O(NW)$個狀態，每次轉移需要$O(k[i])$的平均，總共是$O(NW\sum{k[i]})$，之後會教一些邪惡的優化手段讓$K$變不見
----
### 延伸問題
各種零錢問題像是：有幾種方法湊出指定價格、最少錢幣個數湊出指定價格、最少錢幣種類湊出指定價格...。(例：[CSES1634](https://cses.fi/problemset/task/1634/))
---
## 狀態壓縮
----
當你需要定義的狀態數量有太多個的時候，你可以將好幾個狀態使用一個整數(通常是利用二進制)來表示，例如$dp[2][2][2][2][2]可以變成dp[2^5]$
----
- 例題1：
[atcoder_DP_O](https://atcoder.jp/contests/dp/tasks/dp_o)
----
- 題意：
給定$n$個男人和$n$個女人，告訴你每個男人與每個女人是否相容，需要將所有人配對，使每對都是相容的，且每人只能屬於一對$(n\le 21)$
求可行配對的總數，結果對$10^9+7$取模。
----
- 定義狀態：
$\overbrace{dp[2][2]...[2]}^\text{n項}$，$dp[a_{n}]...[a_2][a_1],a_i\in\{0,1\}$代表考慮到前$\sum{a_i}$個男人且第$a_i$為$1$的女人被選走有幾種可能
例: $dp[0][1][0][1]$為考慮前$2$男且第$0$, $2$女被選走
但是要操作$n$維陣列非常困難，所以可以使用狀態壓縮技巧改成定義$dp[2^n]$，每個整數對應一種狀態$dp[5_{(2)}]$對應到$dp[0][1][0][1]$
----
- 轉移式：
$dp[S]=\sum\limits_{i=1}^{n}{dp[S\oplus i]},\forall\ a[|S|][i]=1$
- 邊界條件：
$dp[0]=1，其他預設為0$
- 答案：
$dp[2^n-1]$
- 時間複雜度分析：
有$O(2^n)$個狀態，每次轉移$O(n)$時間，共需要$O(2^n\cdot n)$時間
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
constexpr int MOD=1e9+7;
vector<vector<int>> edge(25);
int dp[(1<<21)+5]={1};
signed main()
{
//colinorz;
int n,ans=0; cin >> n;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
bool tmp; cin >> tmp;
if (tmp) edge[i].emplace_back(j);
}
for (int msk=1;msk<(1<<n);msk++)
{
int i=__builtin_popcount(msk)-1; //二進制的msk有幾個1
for (int j : edge[i])
if ((msk>>j)&1) dp[msk]=(dp[msk]+dp[msk^(1<<j)])%MOD;
}
cout << dp[(1<<n)-1] << endl;
}
```
----
- 例題2：
[csdc93](https://csdc.tw/problem/93/)
----
- 題意：
求$p$位數且以$q$結尾的快樂數字有幾種，(快樂數字由$1\text{~}9$構成，相鄰兩位相差$\le2$，且$1\text{~}9$皆至少出現一次)，有$n$筆詢問
$(p\le 10^3,\ q\in [1,9],\ n\le 10^4)$
----
- 定義狀態：
$dp[2^9][p][q]$，$dp[S][i][j]($其中$S$的第$k$位為$1$代表$k$有在快樂數字中$)$代表考慮$S$狀態$i$位數$j$結尾的答案
- 轉移式：
$dp[S][i][j]=$
$\sum\limits_{k=j-2}^{j+2}{dp[S][i-1][k]+dp[S\oplus j][i-1][k]}$
$如果S第j位為0，dp[S][i][j]=0$
----
- 邊界條件：
$dp[2^i][1][i]=1,\ i\le 9$，其他預設為0
- 答案：
$dp[2^9-1][p][q]$
- 時間複雜度分析：
預處理有$O(2^{\max(q)}\cdot \max(p)\cdot \max(q))$個狀態，$O(1)$轉移時間，乘起來略小於$10^8$，詢問只需要$O(n)$時間，輕鬆通過
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
constexpr int MOD=1e9+7;
int dp[(1<<9)+3][1005][12]={};
signed main()
{
//colinorz;
for (int j=0;j<=8;j++) dp[(1<<j)][1][j]=1;
for (int msk=1;msk<(1<<9);msk++)
for (int i=2;i<1001;i++)
for (int j=0;j<=8;j++)
{
if (msk&(1<<j)==0) continue;
for (int k=max(0LL,j-2); k<=min(8LL,j+2); k++)
if (msk&(1<<k))
dp[msk][i][j]=(dp[msk][i][j]+dp[msk][i-1][k]+
p[msk^(1<<j)][i-1][k])%MOD;
}
int n; cin >> n;
while (n--)
{
int p,q; cin >> p >> q;
cout << dp[(1<<9)-1][p][q-1] << endl;
}
}
```
----
- 進階題：
[csdc329](https://csdc.tw/problem/329/)
[zj_a086](https://zerojudge.tw/ShowProblem?problemid=a086)
[atcoder_abc187_F](https://atcoder.jp/contests/abc187/tasks/abc187_f) (DP+子集枚舉)
----
csdc329 AC code
```cpp=
```
----
zj_a086 AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
int n,m,cnt=0,ans=0,pcnt[65]={},dp[105][65][65]={};
bitset<12> msk[65]={},a[105]={};
string tmp;
void dfs(int now=-1,bitset<12> s={},int p=0)
{
if (now>=m-3)
{
if (now!=m) s|=(1<<now),p++;
msk[cnt]=s,pcnt[cnt++]=p;
return;
}
if (now!=-1)
{
s|=(1<<now),p++;
for (int i=now+3;i<=m;i++) dfs(i,s,p);
}
else for (int i=0;i<=m;i++) dfs(i,s,p);
}
inline bool lgl(const bitset<12>& a,const bitset<12>& b)
{
return (a&b).none();
}
signed main()
{
//colinorz;
cin >> n >> m; dfs();
for (int i=0;i<n;i++)
{
cin >> tmp;
for (int j=0;j<m;j++) a[i][j]=(tmp[j]=='H'?1:0);
}
for (int j=0;j<cnt;j++)
if (lgl(a[0],msk[j])) dp[0][j][cnt]=pcnt[j];
for (int j=0;j<cnt;j++)
if (lgl(a[1],msk[j])) for (int k=0;k<cnt;k++)
{
if (lgl(a[0],msk[k]) && lgl(msk[k],msk[j]))
dp[1][j][k]=max(dp[1][j][k],dp[0][k][cnt]);
dp[1][j][k]+=pcnt[j];
}
for (int i=2;i<n;i++)
for (int j=0;j<cnt;j++)
if (lgl(msk[j],a[i])) for (int k=0;k<cnt;k++)
{
if (!lgl(msk[k],a[i-1]) || !lgl(msk[k],msk[j])) continue;
for (int l=0;l<cnt;l++)
if (lgl(msk[l],a[i-2]) && lgl(msk[j],msk[l]) && lgl(msk[k],msk[l]))
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]);
dp[i][j][k]+=pcnt[j];
ans=max(ans,dp[i][j][k]);
}
cout << ans << endl;
}
```
----
abc187_F AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
int edge[20][20]={},dp[(1<<18)+5]={},n,m;
signed main()
{
//colinorz;
cin >> n >> m; //[0,n)
for (int i=0;i<n;i++) edge[i][i]=1;
while (m--)
{
int a,b; cin >> a >> b;
edge[a-1][b-1]=edge[b-1][a-1]=1;
}
for (int msk=1;msk<(1<<n);msk++)
{
dp[msk]=1;
for (int i=0;dp[msk]==1 && i<n;i++)
if (msk&(1<<i))
for (int j=0;dp[msk] && j<n;j++)
if (msk&(1<<j) && !edge[i][j]) dp[msk]=1e18;
if (dp[msk]==1) continue;
for (int s=(msk-1)&msk;s ;s=(s-1)&msk)
dp[msk]=min(dp[msk],dp[s]+dp[msk^s]);
}
cout << dp[(1<<n)-1] << endl;
}
```
---
## 練習資源
----
[atcoder_DP](https://atcoder.jp/contests/dp/tasks)
[CSDC_DP](https://csdc.tw/problems/?tag=dp)
[Leetcode_DP](https://leetcode.com/problemset/?topicSlugs=dynamic-programming&page=1)
---
# 謝謝大家
{"title":"進階動態規劃","description":"by: hush","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":20512,\"del\":4259}]"}