Dynamic Programming

動態規劃

搞懂這些一秒變成通靈大師

核心概念及前言
認識DP
DP的時間複雜度&&轉移式
DP實作範例
DP優化

前言及核心概念

前言 – DP 是啥?

動態規劃。透過解決小問題組合成大問題的答案。
DP 題通常難以被其他算法取代，且題型多種多樣。
為什麼會說 DP 是通靈則是因為一定程度的題目通常轉移式都不好求，很吃你的直覺。
遇到DP題的頻率大概為 1-2 題/場，但 台灣站 3 題/場，因此若是你 DP 很強可以拿去說嘴很久。

核心概念 – DP的必知知識

分解 : 將大問題分解成小問題，計算出小問題的答案後再合併出大問題的解
DP(動態規劃) : 分治法的延伸。當分割出來的子問題，一而再、再而三出現，儲存這些問題的答案，避免重複求解，以空間換取時間。
遇到問題-尋找問題分割方法-把大問題遞迴分割成更小的問題-設計計算過程-實作

[尋找問題分割方法]

通常在 DP 裡面，總是可以找到當前狀態的前幾個狀態合併成為當前狀態，而特性如下。

子問題與原問題的求解方式類似。
子問題會一而再、再而三的出現。
子問題以及原問題之間存在一定關係。

[把大問題遞迴分割成更小的問題]

根據以上幾點，尋找到問題之間的關係後，即可分割成小問題去進行求解，求解過程主要是對小問題進行解答後，在根據小問題的答案進行下一步操作。

[設計計算過程]

確認每個問題需要哪些子問題來計算答案。
確認總共有哪些問題。
把問題一一對應到表格。
決定問題的計算順序。
確認初始值、計算範圍。

實作

分別有兩種方式

top-down : 程式碼中採用遞迴結構計算，從大問題往小問題遞迴(因此小問題先被解決)。這個實作方式的好處為只計算必要的問題，以及不必煩惱計算優先順序。
bottom-up : 先理出計算順序，然後由最小的問題開始計算。特色是程式碼通常只有幾個迴圈。這個實作方式的好處為常數較低，且可以自由控制計算順序，也不必擔心 stack overflow(遞迴過多層)

通靈的路上-認識DP

先看過兩題例題，為經典的記憶化搜索

例題Q1. 階乘求解

給你 $q$ 次詢問每次給定數字 $n$ 詢問 $n!$ 為多少

根據前面的步驟，會發現 $n!$ 跟 $n-1$ 的關係為 $(n-1)! * n$

所以就可以分割問題為 $1!,2!,3!,...,(n-1)!,n!$

設計方法則為每一層是前一層 $\times$ 當前層數 [ $(n-1)! * n$ ]

實作方法則在下面做出簡單的範例





void factorial(){
	f[0] = 0; f[1] = 1;
	for (int i=2; i<=N; i++)
		f[i] = f[i-1] * i;
}

分析例題一的時間複雜度以及空間複雜度
時間複雜度 : 總共 N 個問題，每個問題花費 O(1) 時間，總共花費 O(N) 時間。
空間複雜度 : 求 1! 到 N!, 總共 $N$ 個問題，用大小為 $N$ 的陣列儲存全部問題的答案，空間複雜度 $O(N)$

例題Q2 遞迴數學式求解

$q$ ($1$ $\le q \le 2\times 10^5$) 筆詢問
每筆詢問給予一個數字 $n$ ($1$ $\le n \le 10^6$) ，求 $f [ n ]$ 值為多少

思路
首先我們分析暴力做他的時間複雜度。
發現到這樣直接暴力解 $f(n-2)+f(n-1)$ 做會 TLE。
只需要開一個大小為 $10^6$ 的陣列 $dp$ 然後 $dp[i]$ 儲存 $f(i)$ 的結果就好，具體代碼如下。

top-down

int f(int n){
    if (n == 0 || n == 1) return 1;
    // 用 0 代表該問題還未計算答案
    if (table[n]) return table[n];
    return table[n] = f(n-1) + f(n-2);
}

int main(){
    f(N);
    int q;
    while(cin >> q){
        cout << f(q) << '\n';
    }
}

Bottom-up

int main(){
    table[0] = 1;
    table[1] = 1;

    for (int i=2; i<=N; i++)
        table[i] = table[i-1] + table[i-2];
    
    int q;
    while(cin >> q){
        cout << table[q] << '\n';
    }
}

分析例題二的時間複雜度以及空間複雜度
時間複雜度 : 總共 $N$ 個問題，每個問題花費 O(1) 時間，總共花費 O(N) 時間。
空間複雜度 : 求 $1$ 到 $N$,總共 $N$ 個問題，用大小為 $N$ 的陣列儲存全部問題的答案，空間複雜度 O(N)

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的時間/空間複雜度&&轉移式

DP的時間/空間複雜度

簡單的時間複雜度 : 狀態數*轉移複雜度
難的時間複雜度 : 根據每個人會有不同的實作方式去計算
狀態數 : 計算最終答案總共需要用到的子問題數量
轉移複雜度 : 計算任一個子問題的複雜度
空間複雜度 : 很直觀根據你開了多少來確定，應該不用太多描述。

DP的轉移式

轉移式是用來表達 DP 的數學式子，類似遞迴數列的式子
不管你用何種實作方式都可以寫出一種 DP 的轉移式，有些簡單明瞭有些複雜到爆
主要是描述如何用小問題的解計算出大問題的解，也就是大問題跟小問題之間的關係
與 greedy 不同的是 greedy 是一直使用同種策略，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[i]=max(dp[i],dp[j]+1),\forall arr[i] > arr[j]\land i > j$ LIS (最長遞增子序列)
$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}$ LCS (最長公共子序列)

DP 的生命就是轉移式

清楚且完整的表達 DP 的關係
每一個 DP 狀態都有他所代表的東西
從轉移式中可以看出遞迴計算大問題所需要的子狀態與計算方式
大多 DP 可以從轉移式看出總狀態數與轉移複雜度
列出轉移式後，照著打就可以輕鬆的寫出 DP 的程式了(尤其是 top-down)
容易推導 DP 優化

下課時間

DP經典問題實戰

零錢問題
背包問題
最長遞增子序列(LIS)
最長共同子序列(LCS)

零錢問題

題序 : 身上帶太多的零錢會很麻煩，因此會希望店員在找零錢能夠以最少的硬幣數來找，而不是全部都用1元塞給我們。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

也就是要用最少的硬幣數湊出目標數字，具體作法為比較「每個硬幣的面額」與「其次小硬幣的面額」

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

假設需要找$86
【情況1】硬幣有：$50, $10, $5, $1 四種面額，由於每個數字都是次小數字的倍數，因此可以直接用greedy寫掉，從最大的硬幣去選。答案為 50*1 + 10*3 + 5*1 + 1*1 總共六枚

【情況2】硬幣有：$50, $46, $10, $5, $1 五種面額，這時會發現greedy好像怪怪的，因此這時候就需要使用 [ 動態規劃 ] 去完成這題。

top-down

使用遞迴法，分割子問題

目標(原問題): 要算出 86 元的最少硬幣數量

有 $50, $46, $10, $5, $1 這些種類的硬幣
分割為子問題:

先找一個 $50，繼續求剩下的 $36 的最少硬幣數量
先找一個 $46，繼續求剩下的 $40 的最少硬幣數量
先找一個 $10，繼續求剩下的 $76 的最少硬幣數量
先找一個 $5，繼續求剩下的 $81 的最少硬幣數量
先找一個 $1，繼續求剩下的 $85 的最少硬幣數量

透過把大問題分解成更小的問題求解

vector<int> coins = {50, 46, 10, 5, 1};
int minimumChange(int x){
    if(x == 0) return 0;
    int mn = 1e9; // 答案初始設成無限大(不可能達成)
    for(int i : coins){
        if(x >= i){ // 判斷當前要找的錢 x 是否 >= 零錢 i
            // 使用一個大小為 i 的零錢找零，剩下的 $(x - i) 繼續求解
            mn = min(mn, 1 + minimumChange(x - i));
        }
    }
    return mn;
}

過程中會發現同一個值 x 可能會出現很多次

以 76 為例:

$86 - 10 = 76$
$86 - 5 - 5 = 76$
$86 - 1 - 1 - 1 - 1 - 1 - 5 = 76$
$86 - 1 - 1 ... - 1 = 76$

如果每次 minimumChange(76) 都重新求解，則會花費很多時間

回到 DP 的核心概念

當分割出來的子問題，一而再、再而三出現，儲存這些問題的答案，避免重複求解，以空間換取時間。

DP 狀態: $dp[ x ]$ - 紀錄目前要湊成金額 $x$ 的最少硬幣數目。
狀態轉移：當用一個硬幣面額 coins[i] 可以使用更少的硬幣數目來湊成金額 x 時，更新 dp[ $x$ ] = min( dp[ $x$ ], dp[ $x$ – coins[ $i$ ]] + 1)

vector<int> coins = {50, 46, 10, 5, 1};
int dp[100]; // 開大小至少為 n 的表格，紀錄所有會出現的狀態
int minimumChange(int x){
    if(x == 0) return 0;
    if(dp[x])  return dp[x]; // 如果已經計算過了，則直接回傳這個問題的答案
    int mn = 1e9; // 答案初始設成無限大(不可能達成)
    for(int i : coins){
        if(x >= i){ // 判斷當前要找的錢 x 是否 >= 零錢 i
            // 使用一個大小為 i 的零錢找零，剩下的 $(x - i) 繼續求解
            mn = min(mn, 1 + minimumChange(x - i));
        }
    }
    return dp[x] = mn; // 每次算完一個問題的答案，把答案儲存起來
}

時間複雜度

找錢的範圍為 $n$，零錢種類數量 $m$，
$n$ 個問題，每個問題有 $m$ 個轉移
因此時間複雜度為 $O(nm)$

空間複雜度

開了大小為 $n$ $(要找的錢大小)$ 的陣列，複雜度 $O(n)$

bottom-up

$dp[ i ]$：紀錄目前要湊成金額 $x$ 的最少硬幣數目。
初始化 :
$dp[i] = \begin{cases}0, & i = 0\\ \infty, & i > 0\end{cases}$
狀態轉移：當已經知道 $dp[i]$ 最少需要多少硬幣時，使用 coins[j] 更新 dp[i + coins[j]] =
min( dp[i + coins[j]], dp[ i ] + 1 );
時間複雜度 : 找錢的範圍 $n$，零錢種類數量 $m$，總共有 $nm$ 個問題，因此時間複雜度為 $O(nm)$

背包問題

n 個物品儘量塞進背包裡面，令背包裡面的物品總價值最高。背包有重量限制 $w$。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

這就是廣為人知的背包問題，其有許多變形，而本堂課將介紹最經典的 [ 0/1 背包問題 ] 「 0/1 」的意思是：每個物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包。物品無法切割。

看到這種問題若沒學過直覺通常會是貪心，不管是貪心他的價值或是貪心他的 CP 值也好，在這種題目下面都是錯的。

0/1 背包問題的關鍵點，在於如何有效利用背包的剩餘重量，找出最好的物品組合方式。

第一步，分割問題。

然而分割問題的方式很簡單：對某一件物品來說，我們可以選擇放或不放；然後移去這件物品，縮小問題範疇。

一件物品不放進背包，背包價值不變、背包耐重不變；一件物品放進背包，背包價值上升、背包耐重下降。遞迴公式為：
$c$ ($n$, $w$) $=$ $max$$( c(n-1, w)$, $c(n-1, w-weight[n])$ $+$ $cost[n]$ )

就可以依照這個遞迴公式去設計 top-down 的版本
過程中，dp[n][w] 這個狀態是可以記錄的，會不斷重複出現

而 bottom-up 的迴圈版本如下:

for (int i = 0; i < n; ++i)
		for (int j = weight[i]; j <= w; j++)	// 由後往前
			dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i]] + cost[i]);

$dp[ i ][ j ]$：紀錄使用前 $i$ 個元素，背包重量使用了 $j$ 的最大價值。
測試每個物品 $weight[ i ]$ 放或不放
狀態轉移方程：當有一個更好的方法是在同重量下可以獲得更高價值時，更新 $dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i]] + value[i]);$
初始化 : $dp[ i ][ j ] = 0$ $\forall i = 0\sim n, j = 0\sim w$
時間複雜度 : 背包的範圍$N$，物品種類數量$M$，總共有 $NM$ 個問題，因此時間複雜度為 $O(NM)$

最長遞增子序列(LIS)

題序 : 從一連串的整數序列中選出最長的嚴格遞增子序列（strictly longest increasing subsequence）。

例如：在 $\{1, 3, 2, 2, 4, 0\}$ 中 LIS 為
$1, 3, 4$ 或者 $1, 2, 4$。

第一步分割問題 : 記錄第 i 個元素為 LIS 的結尾下的 LIS 長度

第二步設計算法 : 每次檢查位置 $i$ 是否存在任何位置 $j$ $(j < i)$，則 arr[i] 可以接在 arr[j] 後面，dp[i] = dp[j] +1，

範例代碼

int LIS(){
	// 初始化。每一個元素本身就是長度為 1 的 LIS。
	for (int i=0; i<N; i++) dp[i] = 1;

	for (int i=0; i<N; i++)
		// 找出 arr[i] 能接在哪些數字後面
		// 若是可以接，長度就增加。
		for (int j=0; j<i; j++)
			if (arr[j] < arr[i])
				dp[i] = max(dp[i], dp[j] + 1);

	// dp[] 之中最大的值即為 LIS 的長度。
	return *max_element(dp, dp+n);
}

$dp[ i ]$ : 以 $arr[i]$ 為結尾的最長遞增子序列長度
測試每個字串結尾 $arr[ i ]$
狀態轉移方程：當有一個更好的方法是在同長度下可以獲得更長序列時，更新 : $dp[i]=max(dp[i],dp[j]+1)$
初始化：$dp[i]=1$ $(1 \le i \le n)$ 至少選自己長度為 1
時間複雜度 : 狀態數 $O(N)$，轉移複雜度 $O(N)$，總複雜度 $O(N^2)$

最長共同子序列 (LCS)

題序 : 給定兩個字串 $s, t$，求 $s$ 與 $t$ 的最長共同子序列( Longest Common Subsequence )

第一步分割問題，記錄在分別字串前綴 s[0..i] 和 t[0..j] 下的 LCS 長度

第二步設計算法，每次檢查當前的結尾 s[i] 是否與 t[j] 一樣，若是一樣則 $dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1$
否則 $dp[ i ][ j ]$ 就會等於 $max(dp[i-1][j], dp[ i ][ j-1 ]$)

sample

x = "ABCBDAB"
y = "BDCABA"

$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][j]=0$
時間複雜度 : 狀態數$O(n^2)$，轉移複雜度$O(1)$，總複雜度$O(n^2)$
通常為了方便會把 $dp$ 陣列平移，且此 DP 可以滾動

路徑回朔

要尋找哪一個才是合法的 LCS 時，我們就需要紀錄每一個字串的選取，由於每次查找的是 $dp[x-1][y]$ 跟 $dp[x][y-1]$ 哪個長度更長。

最後從 $len1$ , $len2$ 開始往前回溯，輸出最長公共子序列。

範例代碼

string ans;
void trace(int x,int y){
    if(!x&&!y)
        return ;
    if(tag[x][y]==0){
        trace(x-1,y-1);
        ans += s[x-1];
    }
    else if(tag[x][y]==1)
        trace(x-1,y);
    else
        trace(x,y-1);
}
void solve(){
    cin >> s >> t;
    len1 = s.size(), len2 = t.size();
    for(int i = 1; i <= l1; i++)
        tag[i][0]=1;
    for(int i = 1; i <= l2; i++)
        tag[0][i]=-1;
    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {
            if (s[i-1] == t[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                tag[i][j] = 0;
            } 
            else if(dp[i-1][j]>=dp[i][j-1]){
                dp[i][j] = dp[i-1][j];
                tag[i][j] = 1;
            }
            else{
                dp[i][j]=dp[i][j-1];
                tag[i][j] = -1;
            }
        }
    }
    cout << dp[len1][len2] << "\n";
    trace(len1,len2);
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

DP 優化

時間上的優化

有非常多的種類，分別用在不同的情況
單調隊列優化、斜率優化、四邊形優化、分治優化、矩陣快速冪、多項式乘法、aliens 優化…
由於是進階內容，本堂課程內容著重於讓大家認識 DP 以及可以靠自己列出轉移式，因此本堂沒有要教，若已熟知基礎 DP 內容或是對以上優化有興趣都可以再來敲我們問

空間上的優化

滾動 DP 很直覺的優化方式之一

滾動數組的作用在於優化空間。因為 DP 題目是一個自底向上的擴展過程，我們常常需要用到的是線性的解，前面的解往往不用紀錄。所以用滾動數組優化是很有效的。利用滾動數組的話在N很大的情況下可以達到壓縮存儲的作用，通常可以直接壓掉一個維度的大小。

ex: dp[N][M] $\to$ dp[N]

再次拿遞迴數學式來舉例
$f(n)=f(n-1)+f(n-2)$
可以看出計算每一項在計算時，只會用到$dp[n],dp[n-1],dp[n-2]$
因此原本需要開到$N$大的空間數組就不需要開，只需要開3個變數
只能用bottom-up計算，只需要三個變數交替使用$cur,pre,ppre$

int cur,pre=1,ppre=0;
for(int i=2;i<=n;i++)
    cur=pre+ppre,ppre=pre,pre=cur;

滾動 DP 結論

用來節省空間，常常可以節省一個維度
不是所有 DP 都可以滾動
用於 bottom-up，單次計算
從轉移式中看計算每一項所需要用到的子狀態是否有跟著遞增(算到後面，前面的狀態就不會再被使用)

直接實作最後一題 : 二階樓梯記數問題

一個 $n\times n$ 方格棋盤，從左上角走到右下角，每次只能往右走一格或者往下走一格。請問有幾種走法？
example :

第一步分割問題會發現對於任何一個方格來說，只可能「從上走來」或者「從左走來」，答案是兩者相加，也就是說可以從上方以及左方的方格步數推算出當前這格的步數。

設計轉移式 $dp[i][j]$ 代表走到當前 $i$, $j$ 格有幾種方法，因此$dp[i][j] = dp[i-1][j] + dp[i][j-1]$

然後這時候就會發現，他的轉移式只需要用到 $i$ 的前一項或者是 $j$ 的前一項，那是否可以節省空間呢

答案是必然的，如果不需要儲存所有問題的答案，只想要得到其中一個特定問題的答案，那只需要一維陣列就夠了，也就是 O(N) 空間。

for (int i=1; i<N; i++)
		for (int j=1; j<N; j++)
			f[j] += f[j-1];

就成功的作出了空間優化了

總結

DP 是個博大精深的演算法，初學者剛學演算法很快就會碰到，然而難的 DP 也可以到變成防破台

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

也是因為 DP 不論從難度、類型來看，變化都非常多，所以幾乎所有競賽 DP 都扮演很重要的角色(台灣站更是每年 DP 占了都 1/3 的題數)，也因此好好學會 DP 非常的重要!

DP 不算是一個制式的演算法，而是一種概念，因此它的用途/形式多變想學好它不是很容易，要能在在看到題目時有辦法快速辨別能不能 DP / 怎麼 DP 等只能靠多看題目多練習(把各種類型的 DP 都看很多次自然而然就會熟悉模式了(O))

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

Dynamic Programming

動態規劃

搞懂這些 一秒變成通靈大師

前言及核心概念

前言 – DP 是啥?

核心概念 – DP的必知知識

[尋找問題分割方法]

[把大問題遞迴分割成更小的問題]

[設計計算過程]

實作

通靈的路上-認識DP

例題Q2 遞迴數學式求解

top-down

Bottom-up

Top-Down v.s. Bottom-Up

DP的時間/空間 複雜度&&轉移式

DP的時間/空間 複雜度

DP的轉移式

範例

DP 的生命就是轉移式

下課時間

DP經典問題實戰

零錢問題

top-down

回到 DP 的核心概念

時間複雜度

空間複雜度

bottom-up

背包問題

最長遞增子序列(LIS)

最長共同子序列 (LCS)

sample

路徑回朔

DP 優化

時間上的優化

空間上的優化

滾動 DP 很直覺的優化方式之一

滾動 DP 結論

直接實作最後一題 : 二階樓梯記數問題

總結

搞懂這些一秒變成通靈大師

DP的時間/空間複雜度&&轉移式

DP的時間/空間複雜度