# 動態規劃導論 Introduce to Dynamic Programming
這篇來入門競程中最精華、最熱門的主題，動態規劃

## 簡介
### Terminology
DP 代表動態規劃 (Dynamic Programming)，其中，Programming 的意思在這邊並不是我們所熟知到「寫程式」而是「規劃」，意旨規劃空間來解問題的技巧。值得注意的是，動態規劃不是一種演算法，而是一種設計演算法的「技巧」

### 競程中的動態規劃
動態規劃 (DP) 是競程的所有題型當中最熱門的一種。如果你特別會二分搜、貪心法、暴搜，那頂多只是資工系必修的演算法有學好而已。如果你特別會圖論、數論、排列組合，那你頂多只是組合數學比別人好而已。但是，如果你特別會 DP，那就可以宣稱競程實力超強。沒錯，DP 就是如此地有標誌性，打競程不被 DP 荼毒是不可能的事，就像沒吃過魯肉飯就不算到過台灣，是一樣的道理

此外，根據我學長的經驗，在 ICPC 台灣站 DP 出現的頻率大約是 $3~$題$/$場 (整場約 $14$ 題)、高中的 APCS 也差不多每場會出現 $1$ 題 (整場 $4$ 題)，不練真的很虧

### 動態規劃很難嗎?
某種程度上，DP 是最考驗把問題抽象化的關鍵，所以當然很難，難到大多數人都會說 DP 是在通靈，若沒靈感很難把解題方法想出來。事實上也沒有一套方法或可以去設計 DP 的演算法，有時甚至連要不要用都不知道，但還是有些特徵可以去判斷是不是要用 DP

### (或許) 可以使用 DP 的場合
- 在枚舉每種可能時，若有可能找到已算過的答案，可以記錄下來避免重複計算
- 可以把大問題拆成小問題的時候
- 子問題一直重複出現的時候
- 處理最佳化問題 (求最大 or 最小) 的時候
- 當輸入大到不可思議的時候
- 已知遞迴式的時候
- 看不出問題要怎麼解的時候 (?

### 小提醒
廣義上，只要是有使用記憶體存子問題答案的都算是 DP，所以像是最短路徑的那一坨演算法、flow 的那一大坨模板都算是 DP。但，因為那些東西通常不太會去改他們的邏輯，而且套用計算理論那個說法，我們大多時候只是把問題 reduce 到最短路徑或是 flow 的問題上再用相對應的 solver 去解他們，不是重新地去設計一個新的演算法，所以不算競程裡的 DP 問題。在這我們只討論使用 DP 技巧設計演算法的問題

## DP 抽象化
### 有技巧的枚舉暴搜
這邊套用我的演算法老師的說法「動態規劃法就是一種有技巧的暴力法」。嗯怎麼說呢，這句話感覺是這樣，但好像不是這樣。在動態規劃法，我們會把所有的可能都算過一遍，但是為了避免重複算到，我們定義了一種方法將已算過的可能與未算過的可能扯上關係。如此定義，每一種可能就會有先後之分，我們在計算時就需要照著這個順序依序運算，才能得到答案

||如果看過[這篇](https://hackmd.io/@ShanC/topological_sort)應該知道我在鋪成什麼吧!!||

### 遞迴 / 分治法
可以用 DP 解的問題還有一些特徵 :
1. 大問題可以被分割成數個小問題 (大問題 reduce to 小問題)
2. 小問題是可解的 (沒有這個條件就會一直分割問題，變無窮迴圈)
3. 小問題的最佳解可以拿去解大問題 (用小問題的 solver 解大問題)

||讀過圖靈機可解不可解問題應該會很有感吧! 這邊就借用 Turing reduction 的蓋念||

這些性質也可以從數學中的遞迴看出來。舉例來說，若要求費氏數列的第 $n$ 項 $f_n$，那我們可以 :
1. 將 $f_n$ 分割成 $f_{n-1}$ 跟 $f_{n-2}$
2. 對於所有 $n\geq 1$，$f_{n-1}$ 跟 $f_{n-2}$ 必須可以算出來
3. 假設已知 $f_{n-1}$ 與 $f_{n-2}$ 的答案，則可計算 $f_n = f_{n-1} + f_{n-2}$

這裡可能你會覺得是廢話，但別忘了在計算機中，每一個步驟都是很嚴謹的，不可以跳步驟，像是你在設計 DP 演算法時就有可能忽略其實我們並不知道 $f_{n-1}$ 跟 $f_{n-2}$ 的答案，若隨便把兩者加起來，就會壞掉。這種邏輯盲區，就有可能讓你設計出會 WA 的演算法

### 有向無環狀態圖
任何 DP 都可以有向無環狀態圖來呈現。照[前面](###有技巧的枚舉暴搜)的說法，我們可以 :
- 把爆搜的每一種可能當作是一個「狀態」，每個狀態都代表一個子問題
- 用小問題的解算出大問題的解稱為「轉移」

這時你應該要很意外地發現這跟有向圖 (圖論的那個) 的定義一模一樣，所以我們定義 :
- 每個狀態就是一個節點 (vertex)
- 每個轉移是一個有向邊 (directed edge)

如此一來，圖就能被畫出來。我們可以讀一次下面這張圖。狀態 $A$ 可以轉移到狀態 $B$。若我們可以找出 $A$ 的答案，就可以找出 $B$ 的答案


在下面這張圖中，狀態 $f[n-1]$ 跟 $f[n-2]$ 可以轉移到狀態 $f[n]$。若我們能算出 $f[n-1]$ 跟 $f[n-2]$，那就可以算出 $f[n]$。具體例子可以看底下[費氏數列](##Top-down-vs-Bottom-up)的例子


要注意這種有向圖不存在環 (cycle)。可以用反證法說明一下，若一個狀態被轉移幾次後會回到自己，那就代表一個問題的好幾個子問題後會變成自己，這樣在計算上就會進入無限迴圈，因此這種狀況不可以存在

從另一個角度看，若我們定義解掉問題$=$走訪節點，那麼 DP 就是在使用[拓樸排序](https://hackmd.io/@ShanC/topological_sort)的走訪方式遍歷狀態圖!!

## Top-down vs Bottom-up
以上都只是概念，但實作 DP 的話會有兩種不同的方法。舉一個費氏數列的例子，由於我們的轉移式已經定義好的，長這樣 $f_n=\begin{cases}
1,~n\leq1 \\
f_{n-1}+f_{n-2},~otherwise\\
\end{cases}$，所以可以直接得到以下的狀態圖


### 直接照遞迴式寫出函式
這在基礎就講過了，怎麼寫出來的就先不討論

int fib(int n) {
    if(n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

有意思的是，這種寫法就是暴力法窮舉。舉 $n=6$ 為例，我們可以得到以下這樣的樹狀圖


不難發現，有許多子樹都是相同的，因此這種寫法也非常耗時

注意 : 此樹狀圖不等於狀態圖!!

### Top-down 作法
此作法是從我們想求的答案出發，一路拆解成子問題，直到子問題有解再一路往回算。過程中，我們把算過的子問題答案用 $dp$ 陣列記錄起來。這種手法我們叫做 Memoization

int f(int n){
    if (n <= 1) return n;
    if (dp[n]) return dp[n];
    return dp[n] = f(n-1) + f(n-2);
}

會發現這種方法類似 [DFS](https://hackmd.io/@ShanC/bfs_dfs)。其中，我們只有在節點成為[黑點](https://hackmd.io/@ShanC/topological_sort#%E5%90%8D%E8%A9%9E%E5%AE%9A%E7%BE%A9)時，才會去解他，這剛好對應到 (部分的) 拓樸排序演算法的性質，所以這是一個解問題的過程就是拓樸排序。此外，因走訪過的狀態會被 `if (dp[n]) return dp[n];` 這行擋下來，因此不會再次走訪

註 : Memoization 跟 Memorization 不一樣!! Memoization 是有點像做小抄的感覺把東西記起來，Memorization 就只是單純的記憶而已

### Bottom-up 作法
Bottom-up 顧名思義，就是先從子問題出發，先解決子問題再解決更大的問題。在費氏數列中，恰好子問題就是數字比較小的項，所以這樣從小到大解問題是合理的

dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];

照這走訪順序，不難發現解問題的順序其實也是拓樸排序，而且跟 top-down 一模一樣

有人認為 bottom-up 就是填表法，這種觀點因為沒有觸及到這方法的核心，所以感覺是這樣但也好像不是這樣

### 相同之處
- 都可以解出問題
- 若所有狀態都有拜訪，兩者其實都只是對有向無環狀態圖做拓樸排序，只是順序不同
(但是在費式數列的例子剛好相同。如果要看不同的例子，可以看[這篇](https://hackmd.io/@ShanC/interval-dp#%E8%A7%A3%E9%87%8B-3--%E6%9C%89%E5%90%91%E7%84%A1%E7%92%B0%E5%9C%96-DAG-%E7%9A%84%E7%8B%80%E6%85%8B%E8%BD%89%E7%A7%BB))
- 理論時間複雜度相同，因為上限都可以看成是拓樸排序，與拜訪所有狀態的時間相同
(有時候轉移也會耗時，這點要注意)

### 優缺點
#### Top-down
- 想不到解答時，拆解問題會比較直觀
- 因會要使用遞迴，要用到的實際空間與時間會比較多
- top-down 只會計算該次呼叫所需要用到的所有子狀態，可能不會走訪完所有狀態
- 由於不一定會完全走完全部節點，所以可能不能說是拓樸排序 (但順序都會是對的)

#### Bottom-up
- 推出這種解法通常不直觀
- 速度較快
- 一次記算完所有狀態
- 對於狀態很疏鬆的 DP，bottom-up 可能會計算很多冗餘的狀態
- 相當於對狀態圖做拓樸排序的走訪

## 一些小提醒

- 根據我學長 (jakao) 的經驗，若狀態緊密且容易找出計算順序就用 bottom-up (常數小，沒有RE風險)，反之才用 top-down
- 不要覺得狀態一定是從數字小到數字大的，終究還是要看回狀態圖的定義

----

## 參考資料
[海大競程 - Dynamic Programming 動態規劃](https://hackmd.io/@LeeShoWhaodian/2024dp#/)
[海大競程 - Classic DP](https://hackmd.io/@LeeShoWhaodian/Hk8xpN7iyg#/)
[師大演算法筆記 - dynamic programming](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html)
[geeksforgeeks - Dynamic Programming (DP) and Directed Acyclic Graphs (DAG)](https://www.geeksforgeeks.org/dynamic-programming-dp-and-directed-acyclic-graphs-dag/)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/7/10