動態規劃三要素#
動態規劃問題必須同時滿足三個特徵：重叠子問題、無後效性、最優子結構。理解這三個特徵，是判斷問題是否適用 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[i][j] 依賴於 DP[i+1][j-1]、DP[i+1][j]、DP[i][j-1]
# 最終結果在 DP[0][n-1]
# 計算方向：從右下角斜向左上角
for i in range(n-1, -1, -1): # 從大到小
for j in range(i+1, 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$：當前決策與子問題結果的組合