前言 – DP 是啥?

• 動態規劃。透過解決小問題組合成大問題的答案。

• DP 題通常難以被其他算法取代，且題型多種多樣。

• 為什麼會說 DP 是通靈則是因為一定程度的題目通常轉移式都不好求，很吃你的直覺。

• 遇到DP題的頻率大概為 1-2 題/場，但 台灣站 3 題/場，因此若是你 DP 很強可以拿去說嘴很久。

核心概念 – DP的必知知識

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

[尋找問題分割方法]

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

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

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

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

[設計計算過程]

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

實作

分別有兩種方式

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

例題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 的轉移式，有些簡單明瞭有些複雜到爆
• 主要是描述如何用小問題的解計算出大問題的解，也就是大問題跟小問題之間的關係
• 與 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 優化

零錢問題

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

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

假設需要找$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\)。

這就是廣為人知的背包問題，其有許多變形，而本堂課將介紹最經典的 [ 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;
}

時間上的優化

• 有非常多的種類，分別用在不同的情況
• 單調隊列優化、斜率優化、四邊形優化、分治優化、矩陣快速冪、多項式乘法、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 / 怎麼 DP 等只能靠多看題目多練習(把各種類型的 DP 都看很多次自然而然就會熟悉模式了(O))