# 動態規劃優化
by: hush
---
## 內容
----
這堂課主要會教各種dp的優化，通常會去優化轉移的效率，或是優化儲存空間
---
## 前綴和優化
----
- 例題：
[csdc412](https://csdc.tw/problem/412/)
----
- 題意：
有$n$個物品編號$1$~$n$，可以取任意個物品但任意兩物品的編號相差要$\ge m$，求有幾種取法(答案對$10^9+7$取餘)
$1\le m\le n\le 10^6$
----
- 定義狀態：
$dp[n+1]$，$dp[i]$代表考慮前$i$個物品且必須取第$i$個物品有幾種可能
- 轉移式：
$dp[i]=\sum\limits_{j=0}^{i-m}{dp[j]},\ i> m$
----
- 初始條件：
$dp[i]=1,\ 0\le i\le m$
- 答案：
$\sum\limits_{i=0}^{n}{dp[i]}$
----
- 時間複雜度：
有$O(n)$個狀態，每次轉移要$O(n-m)$時間，共要$O(n(n-m))$，最差情況下會TLE需要優化
- 優化方式：
可以前綴和優化，每次算出$dp[i]$就同時維護$pre[i](pre[i]=\sum\limits_{j=0}^{i}{dp[j]}=pre[i-1]+dp[i])$，可以做到$O(1)$轉移
----
- 新的轉移式：
$dp[i]=pre[i-m],\ i>m$
- 甚至可以不用$dp$陣列，只留下$pre$陣列，答案就會是$pre[n]$
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MOD=1000000007;
int pre[1000005]={1};
signed main()
{
int n,m; cin>>n>>m;
for (int i=1;i<=n;i++)
{
if (i<=m) pre[i]=(pre[i-1]+1)%MOD;
else pre[i]=(pre[i-1]+pre[i-m])%MOD;
}
cout<<pre[n]<<'\n';
}
```
----
- 練習題：
[atcoder_DP_M](https://atcoder.jp/contests/dp/tasks/dp_m)
----
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=1000000007;
vector<int> a(105);
vector<vector<int>> dp(105,vector<int>(100005,0));
signed main()
{
//colinorz;
int n,k; cin >> n >> k;
for (int i=1;i<=n;i++) cin >> a[i];
for (int i=0;i<=n;i++)
for (int j=0,sum=0;j<=k;j++)
{
if (i>0) sum=(sum+dp[i-1][j])%MOD;
if (i>0 && j-a[i]-1>=0) sum=(sum-dp[i-1][j-a[i]-1]+MOD)%MOD;
if (j==0) dp[i][j]=1;
else if (i==0) dp[i][j]=0;
else dp[i][j]=sum;
}
cout << dp[n][k] << endl;
}
```
---
## 滾動數組優化
----
- 內容：
很多問題(例：背包問題)的轉移式會長得像
$dp[i]...=dp[i-1]...$醬子
你最多只需要兩個陣列的空間(或一行)
- 用處：
OJ的空間一般只能開到$2\times 10^7$左右，遇到很壞的問題會需要優化空間，把陣列降維
----
- 兩個陣列：
將兩個陣列交替使用，可以使用取餘數
- 一個陣列：
需要注意轉移的方向決定迴圈方向，以下用背包問題舉例
----
無限背包問題：
```cpp=
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])
```
變成
```cpp=
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
```
----
0/1背包問題：
```cpp=
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
```
變成
```cpp=
for (int i=0;i<n;i++)
for (int j=n;j>=0;j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i])
```
為什麼迴圈倒過來跑
----
無限背包的轉移
| i\j | 0 | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- | --- |
| 2 | | | | ▲ | | |
| 3 | | ▲ | | ● | | |
要先更新前面的，所以從迴圈往右
----
0/1背包的轉移
| i\j | 0 | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- | --- |
| 2 | | ▲ | | ▲ | | |
| 3 | | | | ● | | |
前面的不能被蓋掉，後面的沒用，迴圈往左
----
- 挑戰題：
[csdc259](https://csdc.tw/problem/259/)
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[2][10000002]={};
int v[10005],w[10005];
signed main()
{
int n,m,k=0;cin>>n>>m;
for (int i=1;i<=n;i++) cin>>v[i];
for (int i=1;i<=n;i++) cin>>w[i];
for (int i=1;i<=m;i++) if(i>=w[1])dp[1][i]=v[1];
for (int i=2;i<=n;i++,k=(k+1)&1)
for (int j=m;j;j--)
if (j>=w[i])dp[k][j]=max(dp[k][j-w[i]]+v[i],dp[(k+1)&1][j]);
else dp[k][j]=dp[(k+1)&1][j];
cout<<dp[(k+1)&1][m]/3<<'\n';
}
```
---
## 矩陣快速冪
----
- 矩陣乘法介紹：
若 $A$ 為 $m \times n$ 矩陣，$B$ 為 $n \times p$ 矩陣，則它們的乘積 $C = AB$ 為一個 $m \times p$ 的矩陣，其每個元素 $c_{ij}$ 計算方式如下：
$c_{ij} = \sum_{k=1}^{n} a_{ik} \cdot b_{kj}$
這表示 $C$ 的第 $i$ 行第 $j$ 列的元素，是矩陣 $A$ 的第 $i$ 行與矩陣 $B$ 的第 $j$ 列對應元素相乘後的總和。
----
例如考慮兩個數字矩陣：
$A =
\begin{pmatrix}
1 & 2 \\
3 & 4
\end{pmatrix}, \quad
B =
\begin{pmatrix}
5 & 6 \\
7 & 8
\end{pmatrix}$
則它們的乘積 $C = AB$ 為：
$C =
\begin{pmatrix}
1 \cdot 5 + 2 \cdot 7 & 1 \cdot 6 + 2 \cdot 8 \\
3 \cdot 5 + 4 \cdot 7 & 3 \cdot 6 + 4 \cdot 8
\end{pmatrix}$
$=\begin{pmatrix}
19 & 22 \\
43 & 50
\end{pmatrix}$
----
也可以用來表達方程組：
$\left\{
\begin{array}{l}
1x + 2y = 5 \\
3x + 4y = 11 \\
\end{array}
\right.$
將其轉換為矩陣形式：
$\begin{pmatrix}
1 & 2 \\
3 & 4
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix} =
\begin{pmatrix}
5 \\
11
\end{pmatrix}$
----
- 費氏數列的定義為：
$\left\{
\begin{array}{l}
F(n) = F(n-1) + F(n-2)\\
F(n-1) = F(n-1) + 0\\
\end{array}
\right.$
----
- 我們可以將遞迴式轉換成矩陣形式：
$\begin{pmatrix}
F(n) \\
F(n-1)
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
F(n-1) \\
F(n-2)
\end{pmatrix}$
----
- 由此遞推可得：
$\begin{pmatrix}
F(n) \\
F(n-1)
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n-1}
\begin{pmatrix}
F(1) \\
F(0)
\end{pmatrix}$
- 結論：
透過矩陣快速冪方法計算矩陣$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1}$，即可在$O(\log n)$時間內求得答案。
----
- 例題：
[csdc311](https://csdc.tw/problem/311/)
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vvi vector<vector<int>>
using namespace std;
const int MOD=1e9+7;
vvi operator * (const vvi& a,const vvi& b)
{
vvi tmp(a.size(),vector<int>(b[0].size(),0));
for (int i=0;i<a.size();i++)
for (int j=0;j<b[0].size();j++)
for (int k=0;k<b.size();k++)
tmp[i][j]+=(a[i][k]*b[k][j])%MOD;
return tmp;
}
vvi p={{1,1},{1,0}},f={{1,0},{0,1}};
signed main()
{
int n; cin >> n;
if (n==0||n==1) cout << n <<endl;
else
{
for (n--;n>0;n>>=1)
{
if (n&1!=0) f=(f*p);
p=(p*p);
}
cout << f[0][0]%MOD << endl;
}
}
```
----
- 練習題：
[csdc矩陣快速冪](https://csdc.tw/problems/?tag=%E7%9F%A9%E9%99%A3%E5%BF%AB%E9%80%9F%E5%86%AA)
----
csdc410 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;
int n,m,k,s,sum=0;
vector<vector<int>> ans;
vector<vector<int>> operator*(const vector<vector<int>>& a,const vector<vector<int>>& b)
{
fill(ans.begin(),ans.end(),vector<int>(n,0));
for (int i=0;i<a.size();i++)
for (int j=0;j<b[0].size();j++)
for (int k=0;k<b.size();k++)
ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%MOD;
return ans;
}
vector<vector<int>> dp,tmp;
vector<int> init;
signed main()
{
colinorz;
cin >> n >> m >> k;
tmp.resize(n,vector<int>(n,0)),ans.resize(n,vector<int>(n,0)),dp.resize(n,vector<int>(n,0));
for (int i=0;i<n;i++) dp[i][i]=1;
for (int i=0;i<n;i++) tmp[i][(i+1)%n]=1;
while (m--)
{
int a,b; cin >> a >> b;
tmp[a-1][b-1]=1;
}
cin >> s;
init=tmp[s-1];
for (int p=k;p>0;p>>=1)
{
if (p&1) dp=dp*tmp;
tmp=tmp*tmp;
}
for (int i=0;i<n;i++) sum=(sum+dp[s-1][i])%MOD;
cout << sum << endl;
}
```
---
## 單調對列優化
(感謝資芽)
----
給你一個整數序列(長度$n$)，取任意個整數且相鄰兩個距離$\le k$，求取出的最大加總，$O(n)$時間內完成
----
- 定義狀態：
$dp[n+1]$，$dp[i]$代表考慮前$i$個數且必須取第$i$個數的最大加總
- 轉移式：
$dp[i]=a[i]+\max(dp[i-j]),\ j\in [1,k]$
----
- 初始條件：
$dp[0]=0$
- 答案：
$\max(dp[i]),\ i\in [0,n]$
- 時間複雜度：
有$O(n)$個狀態，每次轉移要$O(k)$時間，共要$O(nk)$，最差情況下會TLE需要優化
----
- 優化方式：
注意到如果$i<j,\ dp[i]\le dp[j]$，那$dp[i]$就不需要被考慮了
所以我們用一個容器維護那些需要被考慮的數
- 實作細節：
1.算完$dp[i]$就把push數對$(dp[i],i)$進容器
2.若容器裡所有$dp[j]\le dp[i]$的數對都pop掉
3.最大值會在最前面(index最小的)，pop掉過期的元素就是答案
(此容器為遞減的對列故稱單調對列)
----
- 時間複雜度：
因為一個$dp$值只會被push和pop一次，所以均攤下來維護單調對列和轉移只需要$O(n)$的時間
- 備註：
可以使用deque或是陣列實作，deque較方便但常數大
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:---:|:---:|:---:|:---:|:---:|
| ( ) | ( ) | ( ) | ( ) | ( ) |
$dp[1]=3,\ \text{push}(3,1)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| $(3,1)$ | ( ) | ( ) | ( ) | ( ) |
$dp[1]=3,\ \text{push}(3,1)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| $(3,1)$ | ( ) | ( ) | ( ) | ( ) |
$dp[2]=-2+3,\ \text{push}(1,2)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| $(3,1)$ | $(1,2)$ | ( ) | ( ) | ( ) |
$dp[2]=-2+3,\ \text{push}(1,2)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| $(3,1)$ | $(1,2)$ | ( ) | ( ) | ( ) |
$dp[3]=-1+3,\ \text{push}(2,3)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| $(3,1)$ | $(2,3)$ | ( ) | ( ) | ( ) |
$dp[3]=-1+3,\ \text{push}(2,3)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| $(3,1)$ | $(2,3)$ | ( ) | ( ) | ( ) |
$dp[4]=-2+3,\ \text{push}(1,4)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| $(3,1)$ | $(2,3)$ | $(1,4)$ | ( ) | ( ) |
$dp[4]=-2+3,\ \text{push}(1,4)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| () | $(2,3)$ | $(1,4)$ | () | ( ) |
$dp[5]=2+2,\ \text{push}(4,5)$
----
e.g.: $a[5]=\{\ 3,-2,-1,-2,\ 2\},\ k=3$
| 1 | 2 | 3 | 4 | 5 |
|:-------:|:---:|:---:|:---:|:---:|
| () | $(4,5)$ | () | () | ( ) |
$dp[5]=2+2,\ \text{push}(4,5)$
----
### 有限背包
----
- 轉移式：
$dp[i][j]=\max(dp[i-1][j],dp[i][j-t\cdot w[i]]+$
$t\cdot v[i]),\ t\le k[i]$
- 翻譯：
$dp[i][j]$為往前$k[i]$個$dp值$的最大值(每次跳$w[i]$個)，所以對每個$\mod w[i]$相同的$j$做單調對列DP就可以在$O(NW)$時間內算完
----
- 練習題：
[APCSS_14_P4]()
[zj_a161](https://zerojudge.tw/ShowProblem?problemid=a161)
----
APCSS_14_P4 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;
struct node
{
int w,v,c;
node(int _w,int _v,int _c) {w=_w,v=_v,c=_c;}
};
vector<node> a(1005,node(0,0,0));
int dp[1005][1005];
deque<pii> dq; //(k, dp)
signed main()
{
//colinorz;
memset(dp,0,sizeof(dp));
int n,m; cin >> n;
for (int i=1;i<=n;i++) cin >> a[i].w >> a[i].v >> a[i].c;
cin >> m;
for (int i=1;i<=n;i++)
{
for (int j=0;j<a[i].w;j++)
{
for (int k=j,cnt=0;k<=m;k+=a[i].w,cnt++)
{
if (!dq.empty() && cnt-dq.front().fi>a[i].c) dq.pop_front();
while (!dq.empty() && dp[i-1][k]>=dq.back().se+(cnt-dq.back().fi)*a[i].v) dq.pop_back();
dq.push_back({cnt,dp[i-1][k]});
dp[i][k]=dq.front().se+(cnt-dq.front().fi)*a[i].v;
}
dq.clear();
}
}
cout << dp[n][m] << endl;
}
```
----
zj_a161 AC code
```cpp=
```
---
# 謝謝大家
{"title":"動態規劃優化","description":"by: hsuh","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":15074,\"del\":3893}]"}