動態規劃導論 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 抽象化

有技巧的枚舉暴搜

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

如果看過這篇應該知道我在鋪成什麼吧!!

遞迴 / 分治法

可以用 DP 解的問題還有一些特徵 :

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

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

這些性質也可以從數學中的遞迴看出來。舉例來說，若要求費氏數列的第

$n$ 項

$f_n$，那我們可以 :

1. 將
   $f_n$ 分割成
   $f_{n-1}$ 跟
   $f_{n-2}$
2. 對於所有
   $n\ge 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]$。具體例子可以看底下費氏數列的例子

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

從另一個角度看，若我們定義解掉問題

$=$走訪節點，那麼 DP 就是在使用拓樸排序的走訪方式遍歷狀態圖!!

Top-down vs Bottom-up

以上都只是概念，但實作 DP 的話會有兩種不同的方法。舉一個費氏數列的例子，由於我們的轉移式已經定義好的，長這樣

$f_n=\{\begin{array}{l}1,n\le 1\\ f_{n-1}+f_{n-2},otherwise\end{array}$，所以可以直接得到以下的狀態圖

直接照遞迴式寫出函式

這在基礎就講過了，怎麼寫出來的就先不討論

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。其中，我們只有在節點成為黑點時，才會去解他，這剛好對應到 (部分的) 拓樸排序演算法的性質，所以這是一個解問題的過程就是拓樸排序。此外，因走訪過的狀態會被 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 就是填表法，這種觀點因為沒有觸及到這方法的核心，所以感覺是這樣但也好像不是這樣

相同之處

• 都可以解出問題
• 若所有狀態都有拜訪，兩者其實都只是對有向無環狀態圖做拓樸排序，只是順序不同
  (但是在費式數列的例子剛好相同。如果要看不同的例子，可以看這篇)
• 理論時間複雜度相同，因為上限都可以看成是拓樸排序，與拜訪所有狀態的時間相同
  (有時候轉移也會耗時，這點要注意)

優缺點

Top-down

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

Bottom-up

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

一些小提醒

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

---

參考資料

海大競程 - Dynamic Programming 動態規劃
海大競程 - Classic DP
師大演算法筆記 - dynamic programming
geeksforgeeks - Dynamic Programming (DP) and Directed Acyclic Graphs (DAG)

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2025/7/10