動態規劃三要素#
動態規劃問題必須同時滿足三個特徵：重疊子問題、無後效性、最優子結構。理解這三個特徵，是判斷問題是否適用 DP 的關鍵。
重疊子問題#
定義#
在窮舉過程中（如遞迴），存在重複計算的現象。相同的子問題會被多次求解。
斐波那契數列示例#
F(10)
/ \
F(9) F(8) ← F(8) 被重複計算
/ \ / \
F(8) F(7) F(7) F(6) ← F(7) 被重複計算多次
...何時存在重疊子問題？ 當一個大問題可以分解成多個子問題，而這些子問題之間有交集時，就存在重疊子問題。 這正是備忘錄能發揮作用的地方。
與問題的關係#
重疊子問題規定了經過拆分後的原問題中，子問題與子問題之間的關係：
- 更大子問題可能包含更小子問題的重複計算部分
- 子問題之間可能存在完全相同的情況
無後效性#
定義#
子問題之間的依賴是單向性的。某階段狀態一旦確定，就不受後續決策的影響。
通俗理解#
如果子問題 A 的結果依賴於子問題 B，那麼子問題 B 的結果一定不能直接或間接依賴於 A。
✓ 正確：B → A（A 依賴 B，B 不依賴 A）
✗ 錯誤：B ↔ A（互相依賴，形成迴圈）為什麼無後效性如此重要？ 動態規劃的計算方向是單向的（如從 0 到 n）。 如果第 n 個子問題會影響第 n-1 個子問題的結果，那麼所有依賴於第 n-1 個子問題的結果都需要重新計算。 這樣，DP 對時間複雜度的最佳化就無從談起了。
與計算方向的關係#
無後效性確保了單調的計算方向一定存在：
- 動態規劃的實際計算一定是一棵樹
- 樹的結構可以確保單向依賴
最優子結構#
定義#
子問題之間必須相互獨立，後續的計算可以通過前面的狀態推導出來。
深入理解#
原問題的最優解是由子問題的最優解組成的。
以購物為例：
- 有最優子結構：折扣蘋果 + 折扣香蕉各自獨立計價 ➡️ 總價最低
- 無最優子結構：折扣不能同時享用 ➡️ 無法簡單組合得到最優解
硬幣找零的最優子結構#
原問題：k=11，面值 [5,3]
子問題：k=6 的最少硬幣數 = 2（3+3）
原問題的解：2 + 1（再加一枚 5 元）= 3判斷最優子結構的方法 問自己：如果知道了子問題的最優解，能否通過某種組合方式得到原問題的最優解？ 如果可以，就存在最優子結構。
與狀態轉移方程的關係#
最優子結構規定了子問題與原問題之間的關係：
- 尋找最優子結構的過程，就是證明狀態轉移方程正確性的過程
- 只要寫出狀態轉移方程，問題就解決了一大半
三要素的關係#
mindmap
root((動態規劃問題))
重疊子問題
子問題間的重複關係
備忘錄的基礎
無後效性
子問題間的依賴方向
確保單向計算
最優子結構
子問題與原問題的組合關係
狀態轉移方程的基礎注意：三個條件缺一不可
- 沒有重疊子問題：備忘錄無用，無法最佳化
- 沒有無後效性：計算方向不確定，無法自底向上
- 沒有最優子結構：子問題的解無法組合成原問題的解
統一視角：DP 就是在「狀態圖」上找最佳路徑#
前面把三要素分開講，容易讓人覺得它們是三條互不相干的檢查項。其實只要換一個視角，三者會立刻收攏成同一件事。
把 DP 畫成一張圖#
想像把每個「狀態」當成圖的一個節點，把每一次「狀態轉移」當成一條帶權的有向邊（權重就是這一步決策付出的代價或得到的收益）：
- 節點：一個子問題，例如
DP[i]或DP[i][j]。 - 邊 $u \to v$：從狀態 $u$ 走一步轉移到狀態 $v$，邊權是這步的成本。
- 整張圖通常是一個分層的有向無環圖 (DAG)：層與層之間只往前連、不回頭。
於是「求原問題的最優解」就等於「在這張圖上，找一條從起點（邊界狀態）到終點（目標狀態）的最短／最佳路徑」。
填表順序 = DAG 的拓撲順序 DP 之所以能「自底向上、一格一格填」，是因為這張狀態圖無環。 無環圖必定存在拓撲排序，而我們的「計算方向」要求「算某格時它依賴的格子都已算好」——這恰恰就是按拓撲順序處理節點。 換句話說，每一個正確的填表順序，都是這張 DAG 的一個拓撲序；求最佳路徑的過程，就是 DAG 上的最短路徑（把 min/max 當作邊的鬆弛）。
用這個視角重看兩個要素#
有了「狀態圖」這把尺，最優子結構與無後效性可以被更精準地重新詮釋——這不是另起爐灶，而是把前面講過的話講穿。
最優子結構 ≡ 最佳路徑的任一子段也是最佳的#
路徑詮釋下的最優子結構 設從起點 $S$ 到終點 $T$ 的最佳路徑為 $$P^* = S \to \dots \to u \to \dots \to v \to \dots \to T$$ 那麼其中任一子段 $u \to \dots \to v$，也一定是 $u$ 到 $v$ 的最佳路徑。
用反證法：假設子段 $u \to \dots \to v$ 不是最佳，存在更佳的 $u \rightsquigarrow v$，使 $$w(u \rightsquigarrow v) < w(u \to \dots \to v)$$ 那就用它替換掉 $P^$ 中對應的子段，得到一條從 $S$ 到 $T$ 的整體路徑，其總權重嚴格更小，與「$P^$ 是最佳」矛盾。$\blacksquare$
這就是為什麼「原問題的最優解可由子問題的最優解組成」——子問題的最優解，正是最佳路徑上的那一截子路徑。
無後效性 ≡ 馬可夫性#
無後效性換成路徑語言，就是馬可夫性：
一旦「目前在哪個狀態」確定了，未來能走到哪、各走多少代價，只取決於現在這個狀態本身，而與「是經由哪條路徑走到這裡」無關。
正因為「怎麼來的」不影響「往後怎麼走」，我們才可以對每個狀態只保留一個最佳值（到該狀態的最短距離），用它代表抵達該狀態的所有歷史路徑——這正是 DP 能逐層遞推、把指數級的路徑窮舉壓成多項式的根本原因。若沒有馬可夫性（即有後效性），同一個狀態會因「來路不同」而有不同的後續，單一的最佳值便不足以代表它，遞推也就崩潰了。
看懂這條線，半張地圖就連起來了 一旦接受「DP = 在狀態圖上找最佳路徑」，許多看似獨立的題目其實是同一件事的不同外衣：
- 最短路徑：狀態圖本來就是一張圖，DP 是它在 DAG 上的特例。
- 編輯距離：節點是「字串前綴對 $(i, j)$」，三種操作是三條邊，求的是網格左上到右下的最短路徑。
- 維特比演算法：節點是「某時刻處於某隱藏狀態」，邊權是轉移與發射機率，求的是機率最大的一條路徑。
把它們串成同一條線，你記的就不再是三套模板，而是同一個「狀態圖 + 最佳路徑」的心法。
計算方向詳解#
為什麼計算方向很重要？#
計算方向決定了我們填充 DP 表的順序。錯誤的計算方向會導致：
- 依賴的子問題尚未計算
- 結果錯誤
確定計算方向的方法#
- 找出當前子問題依賴哪些更小的子問題
- 確定最終結果的存儲位置
- 從已知推向未知
示例：最長回文子序列#
// dp[i][j] 依賴於 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]
// 最終結果在 dp[0][n-1]
// 計算方向：從右下角斜向左上角
for (i in n - 1 downTo 0) { // 從大到小
for (j in i + 1 until n) { // 從小到大
// 計算 dp[i][j]
}
}計算方向總結
- 走訪過程中，所需的狀態必須已經計算出來
- 走訪的終點必須是存儲結果的位置
判斷 DP 問題的特徵#
適合使用 DP 的問題類型#
| 類型 | 特徵 | 典型問題 |
|---|---|---|
| 求最優解 | 題目含「最」字 | 最長子序列、最少硬幣 |
| 求可行性 | 問「能否」達成 | 跳躍遊戲、能否湊成 |
| 求方案數 | 問「有多少種」 | 路徑數量、組合數量 |
不適合 DP 的情況#
- 資料可排序：簡單排序就能解決（如找最大的 k 個數）
- 無重疊子問題：如八皇后問題、全排列
- 有後效性：後續決策會影響之前的結果
解題框架總結#
flowchart TD
A[1. 判斷是否為 DP 問題] --> B[2. 確定狀態定義]
B --> C[3. 確定初始化狀態]
C --> D[4. 確定狀態參數]
D --> E[5. 確定狀態轉移方程]
E --> F[6. 確定計算方向]
F --> G[7. 實現程式碼]
A -.- A1[檢查三要素：重疊子問題、無後效性、最優子結構]
B -.- B1["DP[i] 或 DP[i][j] 代表什麼含義"]
C -.- C1[計算的原點，邊界條件]
D -.- D1[會發生變化的變數]
E -.- E1[當前狀態如何從子問題推導]
F -.- F1[確保依賴的狀態已計算]
style A fill:#e3f2fd
style B fill:#e3f2fd
style C fill:#e3f2fd
style D fill:#fff3e0
style E fill:#fff3e0
style F fill:#fff3e0
style G fill:#e8f5e9核心公式（通用框架）
$$ f(x) = \begin{cases} d(x), & x \in V_I \text{ (邊界情況)} \ g({v(f(s(x,c)), c)}), & c \in values(x) \end{cases} $$
- $d(x)$：邊界函式
- $g$：最最佳化函式（min/max）
- $s(x,c)$：子問題參數
- $v$：當前決策與子問題結果的組合