---
tags: FD Training
---
# 動態規劃(Dynamic Programming)
---
## 核心概念
- 分治:將大問題分解成小問題，計算出小問題的答案後再合併出大問題的解
- 以空間換取時間:由於小問題的答案會被多次使用，因此將小問題的答案全部記錄下來
----
### 範例
費氏數列:$f(n)=f(n-1)+f(n-2)$
分治:將$f(n)$分成先計算$f(n-1),f(n-2)$，再相加合併出$f(n)$
$f(n)=f(n-1)+f(n-2)\\=f(n-2)+f(n-3)+f(n-4)+f(n-3)+...$
很明顯的一個子問題可能會被詢問非常多次，因此用陣列紀錄所有$f(i\le n)$的解
----
```cpp
int f(int n)
{
if(n<2) return n;
return f(n-1)+f(n-2);
}
```
```cpp
int dp[1000005]={};
int f(int n)
{
if(n<2) return n;
if(dp[n]) return dp[n];
return dp[n]=f(n-1)+f(n-2);
}
```
$n=45:$後者約0ms，前者約5s
$n=1000000:$後者約0ms，前者至少200000年(?)
實際上後者複雜度$O(n)$，前者是$O(\varphi^n)$(其中$\varphi$是黃金比例)
---
## DP的時間複雜度
簡單的:狀態數\*轉移複雜度
難的:自己通靈
狀態數:計算最終答案總共需要用到的子問題數量
轉移複雜度:計算任一個子問題的複雜度
----
### DP轉移式
- 轉移式是用來表達DP的數學式子，類似遞迴數列的式子
- 主要是描述如何用小問題的解計算出大問題的解
----
### 範例
- $f(n)=f(n-1)+f(n-2)$
- $dp[i]=\max\limits_{0\le j\lt i,i-j<=k}\{dp[j]+a[i]\}$
- $dp[i][j]=\max({dp[i-1][j],dp[i-1][j-w[i]]+c[i]})$
- $dp[p][n]=\min\limits_{0\le i\lt n}\{\max(dp[p-1][i],a[n]-a[i+1])\}$
- $dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}$
----
### DP轉移式的重要性
- 清楚且完整的表達DP
- 從轉移式中可以看出遞迴計算大問題所需要的子狀態與計算方式
- 大多DP可以從轉移式看出總狀態數與轉移複雜度
- 列出轉移式後，照著打就可以輕鬆的寫出DP的程式了(尤其top-down)
- 容易推導dp優化
----
### DP複雜度計算
- ex: $f(n)=f(n-1)+f(n-2)$
狀態數:$O(n)$，轉移複雜度:$O(1)\Rightarrow$總複雜度$O(n)$
- ex: $dp[i]=\max\limits_{0\le j\lt i,i-j<=k}\{dp[j]+a[i]\}$
狀態數:$O(n)$，轉移複雜度:$O(k)\Rightarrow$總複雜度$O(nk)=O(n^2)$
----
- ex: $dp[i][j]=\max({dp[i-1][j],dp[i-1][j-w[i]]+c[i]})$
狀態數:$O(nw)$，轉移複雜度:$O(1)\Rightarrow$總複雜度$O(nw)$
- ex: $dp[p][n]=\min\limits_{0\le i\lt n}\{\max(dp[p-1][i],a[n]-a[i+1])\}$
狀態數:$O(pn)$，轉移複雜度:$O(n)\Rightarrow$總複雜度$O(pn^2)$
- ex: $dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}$
狀態數:$O(n^2)$，轉移複雜度:$O(1)\Rightarrow$總複雜度$O(n^2)$
----
### 如何設計DP?
1. 設計狀態，先決定好要計算的東西(實際意義)與其參數
2. 試著將任一狀態的答案用子狀態來表達(當然也要想清楚正確性)
3. 列出轉移式(將2.的結果清楚寫下來)
4. 確定其複雜度是否是好的
5. DP優化(?)
---
## DP實作
----
### Top-Down
- 由上而下計算，通常以遞迴方式實作
- 一開始所有狀態皆未計算(基本狀態除外)
- 當某個狀態被呼叫時，若該狀態已計算過就從記錄中直接回傳答案，反之則須遞迴計算，並記錄答案
- ex:
```cpp
int dp[1000005]={};
int f(int n)
{
if(n<2) return n;
if(dp[n]) return dp[n];
return dp[n]=f(n-1)+f(n-2);
}
```
----
### Bottom-Up
- 由下而上計算，通常以迴圈方式實作
- 找出一種"好的"計算順序，依此順序一次計算完所有狀態
- "好的計算順序"指的是當你要計算某個狀態時，其需要用到的子狀態答案皆已計算完畢
- ex:
```cpp
int dp[1000005]={};
dp[0]=0,dp[1]=1;
for(int i=2;i<=1000000;i++)
dp[i]=dp[i-1]+dp[i-2];
```
----
### Top-Down v.s. Bottom-Up
- 理論上兩者時間複雜度相同，但前者用遞迴實作通常常數較大
- 對於top-down，若一開始直接呼叫很大的狀態可能會stack overflow
- bottom-up需要找出好的計算順序，對於有些DP不易找到
- top-down只會計算該次呼叫所需要用到的所有子狀態，而bottom-up一次記算完所有子狀態
- 對於狀態很疏鬆的DP，bottom-up可能會計算很多冗餘的狀態
----
- 如果狀態緊密且容易找出計算順序就用bottom-up(常數小，沒有RE風險)
- 反之才用top-down
- 大多DP都是由小計算到大因此容易找順序，除了少數DP有很奇怪的轉移式
- 大多DP狀態都是滿的，通常是暴搜的記憶化搜索才會是疏鬆的狀態
---
## DP優化
----
### 時間上的優化
- 有非常多的種類，分別用在不同的情況
- 單調隊列優化、斜率優化、四邊形優化、分治優化、矩陣快速冪、多項式乘法、aliens優化...
- 又難又難，沒有要教
----
### 空間上的優化
#### 滾動DP
----
- 再次拿費氏數列來舉例
- $f(n)=f(n-1)+f(n-2)$
- 可以看出計算每一項皆只需保留前兩項的答案
- 若用bottom-up計算，只需要三個變數交替使用$cur,pre,ppre$
```cpp
int cur,pre=1,ppre=0;
for(int i=2;i<=n;i++)
cur=pre+ppre,ppre=pre,pre=cur;
```
----
### 滾動DP
- 用來節省空間，常常可以節省一個維度
- 不是所有DP都可以滾動
- 用於bottom-up，單次計算
- 從轉移式中看計算每一項所需要用到的子狀態是否有跟著遞增(算到後面，前面的狀態就不會再被使用)
----
### 舉例
- $f(n)=f(n-1)+f(n-2)$ 只需要保留前兩項
- $dp[i][j]=\max({dp[i-1][j],dp[i-1][j-w[i]]+c[i]})$
只需保留前一列(計算dp[i][...]時只需用到dp[i-1][...])
- $dp[i]=\max\limits_{0\le j\lt i,i-j<=k}\{dp[j]+a[i]\}$
只需保留前$k$項(計算dp[i]時只需用到dp[i-k]...dp[i-1])
- $dp[i]=\max\limits_{0\le j\lt i,i-j>=k}\{dp[j]+a[i]\}$
無法滾動(計算dp[i]時需用到dp[0]...dp[i-k]，永遠不會有"過期"的元素)
---
## 經典DP題
----
### 最大子陣列和(最大區間和)
給定一個數列$a_0,a_1,...,a_{n-1}$，求出區間$l,r$使得區間和$a_l+...+a_r$最大
解法:
令$dp[i]$代表以$a[i]$為結尾最大的區間和
轉移式:$dp[i]=max(dp[i-1]+a[i],a[i])=max(dp[i-1],0)+a[i]$
狀態數$O(n)$，轉移複雜度$O(1)$，總複雜度$O(n)$
此DP可以滾動
----
### 最長共同子序列(LCS)
Longest Common Subsequence
給定兩個字串$s,t$，求$s與t$的最長共同子序列
解法:
令$dp[i][j]$代表字串前綴$s_{0...i}$與$t_{0...j}$的LCS
轉移式:$dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}$
邊界條件:$dp[i][-1]=dp[-1][j]=0$
狀態數$O(n^2)$，轉移複雜度$O(1)$，總複雜度$O(n^2)$
通常為了方便會把$dp$陣列平移，且此DP可以滾動
----
## 矩陣鏈乘積
給定$n$個矩陣$M_i$的大小$r[i]\times c[i]$，求計算所有矩陣相乘$M_1M_2...M_n$最少需要用到多少次乘法(保證所有$c[i]=r[i+1]$)(已知$a\times b$與$b\times c$的矩陣相乘需要$a\times b\times c$次乘法，並變成$a\times c$的矩陣)
解法:
令$dp[l][r]$代表$M_l...M_r$最少需要幾次乘法
轉移式:$dp[l][r]=\min\limits_{l\le i\lt r}\{dp[l][i]+dp[i+1][r]+r[l]\cdot c[l]\cdot c[r]\}$
邊界條件:$dp[i][i]=0$
狀態數$O(n^2)$，轉移複雜度$O(n)$，總複雜度$O(n^3)$
----
### 0/1背包問題(knapsack)
有$N$個物品，第$i$個物品重量$w_i$，價值$p_i$，現在有一個耐重$W$的背包，你可以選一些物品放進去，每個物品只能選或不選(不能取部分)，求最大價值。
解法:
令$dp[i][j]$為考慮前$i$個物品，總重量$\le j$的最大價值
轉移式:$dp[i][j]=\begin{cases}max(dp[i-1][j],dp[i-1][j-w_i]+p_i),j\ge w_i\\dp[i-1][j],j\lt w_i\end{cases}$
狀態數$O(NW)$，轉移複雜度$O(1)$，總複雜度$O(NW)$
----
可以發現此DP轉移所需的子狀態為左上角或正上方的狀態，因此若改變$j$的計算順序(由大計算到小)則可以滾動成只用一個陣列，其中陣列中$>j$的項是已計算完第$i$項(也就是等同$dp[i][...]$)，而$\le j$的項是尚未計算(也就是等同$dp[i-1][...]$
滾動後轉移式:$dp[j]=\begin{cases}max(dp[j],dp[j-w_i]+p_i),j\ge w_i\\dp[j],j\lt w_i\end{cases}$
----
除此之外若計算順序是$j$由小到大則變成是解"**無限背包問題**"，也就是上述問題，但每個物品都有無限多個
轉移式:$dp[i][j]=\max\limits_{w_i\cdot k\le j}\{dp[i-1][j-w_i\cdot k]+p_i\cdot k\}\\=\begin{cases}max(dp[i-1][j],dp[i][j-w_i]+p_i),j\ge w_i\\dp[i-1][j],j\lt w_i\end{cases}$
狀態數$O(NW)$，轉移複雜度$O(1)$，總複雜度$O(NW)$
----
若每項物品的規定改成最多能選$c_i$個則稱作"**多重背包問題**"
基本作法是把第$i$個物品複製$c_i$次做0/1背包問題，複雜度$O(NWC)$
進階做法是把第$i$個物品分堆成$1,2,4,8,...$(總和$=c_i$)，根據二進制可以知道這樣的分堆可以湊出任何數量，因此將所有物品分堆後再做0/1背包問題，複雜度$O(NW\lg C)$
最難的做法是有DP優化可以做到$O(NW)$，超出範圍
---
## 總結
DP是個博大精深的演算法，初學者剛學演算法很快就會碰到DP，然而難的DP也可以難到很可怕 :poop: 也是因為DP不論從難度還是類型來看，變化都非常多，所以幾乎所有的程式設計競賽DP都扮演很重要的角色(北二區學科能力競賽更是連續出了好幾年DP)，也因此好好學會DP非常的重要!
DP不算是一個制式的演算法，而是一種概念，因此它的用途/形式多變想學好它不是很容易，要能在在看到題目時有辦法快速辨別能不能DP/怎麼DP等只能靠多看題目多練習(把各種類型的DP都看很多次自然而然就會熟悉模式了(O)) :poop:
記得設計DP的步驟: 設狀態$\Rightarrow$列轉移$\Rightarrow$算複雜度$\Rightarrow$考慮優化$\Rightarrow$實作出來XD
Sign in with Wallet
Connect another wallet