如果說有一個演算法思想能把頂尖競賽選手與其他人區分開來，那一定是動態規劃：它能把緩慢、重複的暴力列舉轉化為高效、有條理的運算。
動態規劃（DP）是競賽程式設計中的動態規劃裡最重要、也最讓人望而生畏的主題之一。好消息是，DP 並不是什麼魔法。一旦學生理解了讓它成立的兩個條件，以及那些一再出現的少數幾種模式，它就會從靠猜的遊戲變成一件可靠的工具。本指南將依照我們在競賽程式設計課程中的講法，拆解其核心思想。
動態規劃究竟是什麼
動態規劃是一種解題方法：把一個問題拆分成更小的重疊子問題，每個子問題只求解一次，並把答案儲存起來，從而永遠不必重新計算。當一個問題具備以下兩個性質時，它就很適合用 DP：
- 最佳子結構：整個問題的最佳答案可以由其子問題的最佳答案構建而來。
- 重疊子問題：同樣的較小子問題會反覆出現，因此快取它們的結果能節省大量工作。
把它與普通遞迴對比一下。對費氏數列的樸素遞迴解法會以指數級的次數重複計算相同的值。DP 把每個值只存一次，從而把指數級的工作量壓縮為線性級。從重複計算到複用結果的這一轉變，正是它的全部要義。
記憶化與遞推填表
實作 DP 解法有兩種標準方式，兩者計算出的答案相同。
由上而下（記憶化）
你先寫出自然的遞迴解法，然後加上一個快取。在計算一個子問題之前，先檢查它的答案是否已經儲存；如果已儲存，就立即回傳。這種方法很直觀，因為它與你口頭描述問題的方式一致，而且只會計算你實際需要的那些狀態。
由下而上（遞推填表）
你先求解最小的子問題，並按順序填表，逐步構建出完整答案。遞推填表避免了遞迴開銷，也便於推導時間和記憶體，這在比賽限制緊張時尤為重要。優秀的選手兩者都會學，並根據問題來選擇。
無論選哪種，設計工作都是一樣的。先定義狀態（表中單個條目的含義），再寫出轉移（如何由更小的狀態計算出某個狀態），並設定初始情形。把這三點定好，程式碼幾乎會自己寫出來。
反覆出現的模式
大多數比賽中的 DP 題都是一小批經典範本的變體。認出範本，問題就解決了一半：
- 0/1 背包：在重量限制下選取一部分物品以最大化價值。
- 最長遞增子序列（LIS）：找出按遞增順序排列的最長一段值。
- 最長共同子序列與編輯距離：比較兩個序列。
- 硬幣找零：統計湊出某個總額的方案數，或求所需硬幣的最少數量。
- 區間 DP：在陣列的區間上進行最佳化，例如矩陣鏈相乘一類的問題。
- 數位 DP 與位元遮罩 DP：統計具有特定數位性質的數，或緊湊地追蹤子集。
把這些練到形成本能，就能建立起選手們在時間壓力下所依賴的模式識別能力。
DP 在真實比賽中的體現
在 USA Computing Olympiad 中，比賽分為四個組別：Bronze、Silver、Gold 和 Platinum。根據 USACO 官方網站，每位選手都從 Bronze 起步，並透過達到各場比賽而定的晉級分數線獲得晉升。動態規劃在 Gold 級別及以上成為核心；大多數 Gold 和 Platinum 比賽都至少包含一道 DP 題，而這項技術一直到國際資訊學奧林匹亞競賽都不可或缺。比賽形式、計分方式、組別晉級線以及成績認證規則可能逐年變化，因此請務必在 USACO 官方網站上確認當前的具體細節。
能夠晉級的選手，並不是那些背程式碼的人。他們是那些能看著一道新題，迅速識別出狀態與轉移的人。
這種能力是可以教會的。透過有結構的練習，一個今天對 DP 望而生畏的學生，幾個月內就能從容地設計狀態。在 BIAA（標奧），我們一步步培養這種直覺，從最初的遞迴一直到進階最佳化。歡迎在我們的部落格上探索更多指南，或前往我們的競賽程式設計課程頁面，了解我們如何指導學生邁向 Gold 乃至更高的層級。