# 動態規劃
Dynamic Programming(簡稱DP)，基本上是分治法+Memoization
## 如何學好DP
DP只是一種觀念，用途極廣，因此要熟練DP，最重要的是多刷題。
DP最重要的就是如何定狀態，沒有狀態就不用DP了，複雜度跟暴力枚舉沒什麼兩樣。
刷題建議不要找DP題單來刷，這樣會完全無法訓練「如何看出一題是不是DP」的能力。
## 分治法
把一個問題分割成更小的問題，小到答案非常明顯，之後合併。
因為大問題跟小問題本質上是同一種問題，所以常常用遞迴實現
### merge sort
分治法的經典應用。要排序一個數列，可以把原數列切成兩半，之後排序兩個小數列，最後再把排序完的兩個小數列合併。
首先思考，什麼時候可以停止切下去呢?如果數列只剩一項，那麼它顯然就是一個已排序數列
```cpp!
vector<int> Divide(vector<int> v){
if(v.size()>1){
int M=v.size()/2;
vector<int> a=Divide(vector<int>(v.begin(),v.begin()+M));
vector<int> b=Divide(vector<int>(v.begin()+M,v.end()));
v=Merge(a,b);
}
return v;
}
```
接著，要怎麼快速的合併兩個已經排序(由小到大)的數列呢?
只要每次比較兩個小數列的第一項取出最小值即可，複雜度$O(n)$
```cpp
vector<int> Merge(vector<int> a,vector<int> b){
a.push_back(1e9);
b.push_back(1e9);
int a_index=0,b_index=0;
vector<int> v;
while(a_index!=a.size()-1 || b_index!=b.size()-1){
if(a[a_index]<b[b_index]){
v.push_back(a[a_index]);
a_index++;
}
else{
v.push_back(b[b_index]);
b_index++;
}
}
return v;
}
```
示意圖:
[圖源](https://levelup.gitconnected.com/merge-sort-656f8ee59d83)
總複雜度$O(nlogn)$，是非常快的排序法
## Memoization
在做DP的時候，分割出來的子問題可能一再出現，所以用陣列把答案存下來，下次再遇到可以直接$O(1)$回答。在[遞迴](https://hackmd.io/KHyaIm1eT6uDS_XKFFptDw)裡也有講過
## 背包問題
[cses:book shop](https://cses.fi/problemset/task/1158/)
DP的經典問題。你有一個背包，以及$n$個重量為$w_i$，價值為$v_i$的物品。已知背包能裝的總重為$W$，求背包能裝的最大價值?
如果我們定義$dp[i]=背包重量不超過i時的最大價值$，那麼所求的答案就是$dp[w]$
假設我們要在現有的背包加入一個物品$k$，那麼$$dp[i+w_k]=max(dp[i+w_k],dp[i]+v_k)$$也就是說，在重量為$i$的時候，如果放入物品$k$後的價值比較高，那就更新放入後的最大價值。這條式子稱為狀態轉移方程，也就是用比較小的狀態($dp[i]$)來得出大的狀態($dp[i+w_k]$)
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,x;
cin>>n>>x;
vector<int> v(n),w(n),dp(x+1);
for(int i=0;i<n;i++) cin>>w[i];
for(int i=0;i<n;i++) cin>>v[i];
for(int i=0;i<n;i++){
for(int j=x-w[i];j>=0;j--){ //倒著跑
dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i]);
}
}
cout<<dp[x];
return 0;
}
```
注意第二層迴圈要倒著跑，不然一個物品可能會更新很多次。例如:$在j=0時，w_i被更新過；迴圈跑到j=w_i時，又用更新過的j去更新j+w_i$
### 練習題
[cses:Dice Combinations](https://cses.fi/problemset/task/1633/)
給一個數字$n$，用1~6組合有幾種方法?
ex: 3有四種:{ 1+1+1 , 1+2 , 2+1 , 3 }
題解:對於一個數字$n$，只有可能是$(n-1)+1,(n-2)+2...$六種方法。定義$dp[i]=數字i$的方法數，那麼$$dp[i]= \sum_{k=1}^{6}dp[i-k]$$
```cpp
int dp(int n){
if(n<0) return 0;
if(v[n]) return v[n];
int sum=0;
for(int i=n-6;i<n;i++){
sum+=dp(i);
}
v[n]=sum;
return v[n];
}
```
因為$dp(n)$可能被呼叫多次，所以用陣列v把算過的答案存起來
## 優化
### 矩陣優化
當轉移式可以用前幾項表達時，通常可以配成矩陣
例如剛剛那題可以配成:
$$
\begin{bmatrix} 1&1&1&1&1&1 \\ 1&0&0&0&0&0 \\ 0&1&0&0&0&0 \\ 0&0&1&0&0&0 \\ 0&0&0&1&0&0 \\ 0&0&0&0&1&0\end{bmatrix} \times \begin{bmatrix} dp(i-1) \\ dp(i-2) \\ dp(i-3) \\ dp(i-4) \\ dp(i-5) \\ dp(i-6) \end{bmatrix}=
\begin{bmatrix}dp(i) \\ dp(i-1) \\ dp(i-2) \\ dp(i-3) \\ dp(i-4) \\ dp(i-5)\end{bmatrix}$$
推成一般式:
$$
\begin{bmatrix} 1&1&1&1&1&1 \\ 1&0&0&0&0&0 \\ 0&1&0&0&0&0 \\ 0&0&1&0&0&0 \\ 0&0&0&1&0&0 \\ 0&0&0&0&1&0\end{bmatrix}^n \times \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}=
\begin{bmatrix}dp(i) \\ dp(i-1) \\ dp(i-2) \\ dp(i-3) \\ dp(i-4) \\ dp(i-5)\end{bmatrix}$$
複雜度$O(k^3logn)$，其中$k$為矩陣行數
具體見[遞迴](https://hackmd.io/KHyaIm1eT6uDS_XKFFptDw)
### 單調隊列優化
有時對於一個狀態，可能從前面任一個狀態轉移過來，例如：
$$dp[i]=\displaystyle\min_{j<i}\{dp[j]+f(i,j)\}$$
這個時候，使 $dp[i]$ 最小的 $j$ 稱為決策點。如果所有決策點具有單調性(遞增或遞減)的話，例如:
| $i$ (狀態) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| - | - | - |- | - |- | - |- | - |
| $j$ (決策) | 0 | 1 | 1 | 1 | 3 | 3 | 6 | 6 |
如上表，$[2,4]$ 就稱為決策1的區間。
那麼我們可以用一個單調隊列(monotonous queue)來儲存決策區間。要加入一個決策時，如果當前決策的左端點比尾部的左端點小時，可以刪除尾部；反之，如果當前決策的右端點比尾部的右端點大時，可以刪除當前決策。接著，只要找出第一個當前決策比尾部小的點即可，又因為決策有單調性，所以可以使用二分搜。
如此一來，本來是$O(n^2)$的DP被優化成$O(nlogn)$
### 例題
[CSES Maximum Subarray Sum II](https://cses.fi/problemset/task/1644)
(其實這只有單調隊列，不太能算DP)
定義 $dp[j] = \displaystyle\max_{a\leq j-i\leq b}\{pref_j-pref_i\}$ ，其中$pref_i$表示陣列前 $i$ 項的總和，特別定義 $pref_0=0$。
則答案就是$\max\left(dp[1],dp[2],\dots,dp[n]\right)$
對於每個 $j$ ， $pref_j$都是定值，因此我們只需要找到使得 $pref_i$ 最小的 $i$ 即可，而透過觀察可以發現一個重要性質：
**「對於每個 $j$ ，最佳的 $i$ 必定呈非嚴格遞增」**
因此可以套用單調隊列算法：
用deque維護「對於目前的 $j$ ，最好的 $pref_i$」，我們用for迴圈由小到大遞增的跑過所有的 $j$ ，每圈的開始，我們先把所有「已經過期的 $i~(j-i > b)$ 」 從deque前端刪掉，然後讓 $pref_{j-a}$ 不斷的跟deque尾端的值比較，如果 $pref_{j-a}$ 比deque尾端的值還小，那目前的deque尾端的值就是「沒用的」，因為這個值不但比 $pref_{j-a}$ 還要早過期，拿它的值算出來的 $pref_j-pref_i$ 還更小，我們必須把它pop掉，反之則比較結束，在deque尾端此時的值過期之前，拿 $pref_{j-a}$ 算出來的 $pref_j-pref_i$ 都不會是最好的，的把 $pref_{j-a}$ 加進deque的後端之後， $dp[j]$ 就會是 $pref_j-deque.front()$ 了。
本題因為決策覆蓋區間的特性$（i的區間一定從i+1開始）$，所以不需要二分搜，複雜度$O(n)$
有二分搜的版本見[玩具裝箱](https://www.luogu.com.cn/problem/P3195)(這就有DP了)
單調隊列性質：
可以發現，上述算法中的deque的值滿足「deque越前端的值，越早過期，但值越好」，知道這個性質可以讓實作單調隊列更加簡單，更不容易把大小於弄反。
### 斜率優化
一個常見的DP式:
$$dp[i]=\displaystyle\min_{j<i}\{a[j]*b[i]+c[j]\}$$
這時，如果我們定義直線$f_j(x)=a[j]*x+c[j]$，那麼:
$$dp[i]=\displaystyle\min_{j<i}\{f_j(b[i])\}$$也就是說，$dp[i]$現在是從$j$條直線中選出$x=b[i]$的最小值
如圖，$b_i$的最小值在$L_2$上，代表狀態$i$的決策為$2$。另外，我們把$b_i$稱為$i$的查詢
如圖，藍色斜線部分稱為$L_2$的查詢區間，也就是說，當$b_i$在查詢區間中的時候，最小值會發生在$L_2$
#### 斜率單調
因為斜率是遞減的，所以如果$f_a(x_i)>f_b(x_i),a>b$，那麼當$x>x_i$時，$f_a(x)$一定也會大於$f_b(x)$，也就是說，查詢區間是遞增的!要維護遞增的區間，又輪到單調隊列上場了。
#### 查詢單調
如果查詢是遞增的，那麼每次插入前，可以把查詢區間小於目前查詢的線從前面刪掉，因為不可能再查回去了。這樣一來，隊頭的直線就會是當前的決策。想法很像上面單調列隊的例題。
插入的時候，要把尾端不可能成為最小值的線刪掉。思考兩條線的情形:
如圖，$L_2$的查詢區間會是$x$($L_1和L_2的交點$x$座標$)以後
這時插入$L_3$，會有兩種情況:
這種情況下，$L_1L_2L_3$都有查詢區間，直接插入沒有問題
這個時候，會發現$L_2$的查詢區間整個不見，所以可以把$L_2$刪掉
要判斷能不能刪掉$L_2$，只需要判斷它的查詢區間有沒有被覆蓋，觀察圖會發現，一條線的查詢範圍就是跟前一條線的交點到後一條線的交點。設$x_{ab}$為$a和b$的交點$x$，那麼$L_2$的區間為$[x_{12},x_{23}]$。如果$x_{12}>x_{23}$的話，$L_2$顯然沒有查詢區間。
整個算法基本上就像上面單調列隊的例題，複雜度一樣$O(n)$
#### 查詢不單調
查詢不單調的差別就是因為查詢可能查回去比較小的值，所以隊頭的線不能亂刪，以後還有可能用到。這樣我們就不能直接拿隊頭的線當決策了。
設$i$為我們要找的線(最小值會發生的線)，當前查詢是$s$，因為查詢區間遞增，所以:$$f_1(s)...f_{i-2}(s)>f_{i-1}(s)>f_i(s)<f_{i+1}(s)<f_{i+2}(s)...$$
其實看圖也會發現。這時候我們要找的就是單峰函數的極值。
在中間切兩刀，如果$f(a+1)<f(a)$的話，極值在$a$右邊；反過來則在左邊。基本上就是二分搜。總共要搜$n$次，複雜度$O(nlogn)$
這種求極值的搜尋有一種特化的二分搜，叫黃金切割搜，有興趣可以查查看。
#### 斜率不單調
需要使用李超線段樹。有一點難，之後時間夠的話有可能會教。
<!-- 你確定你要教李超線段樹？ 我不確定-->
### 例題
[cses:Monster Game](https://cses.fi/problemset/task/2084/)
Sign in with Wallet
Connect another wallet