既有教材把動態規劃嵌在個別問題裡：0/1 背包、子集和、編輯距離、漢彌爾頓路徑的狀態壓縮。本篇把「怎麼設計一題 DP」抽成可遷移的方法：狀態、轉移、順序、還原方案。讀完再回去看那些專題，會知道它們只是同一套骨架的不同填法。
相關教材：02_Knapsack_Teaching_Materials.tex、03_SubsetSum_Partition_Teaching_Materials.tex、08_HamiltonianPath_Teaching_Materials.tex、Fuzzy_Search_Complete_Teaching_Materials.md（編輯距離與 LCS）、Recursion_Teaching_Materials.md（記憶化）。
目錄
1. 它和分治差在哪
分治把問題切成互不重疊的子問題，各自解決再合併。合併排序的左右兩半沒有共用的子陣列。
動態規劃的子問題會重複出現。朴素遞迴的費氏數列：
[ F(5) = F(4)+F(3),\quad F(4)=F(3)+F(2) ]
F(3) 被算了兩次，更小的又被算更多次，總時間是指數。把每個 F(k) 的答案存起來，每個子問題只算一次，時間變成線性。
所以 DP 不是「用表格的分治」，而是「子問題重疊，所以用表格（或備忘錄）把指數遞迴壓成多項式」。
2. 兩個必要條件
- 最佳子結構：原問題的最佳解，由子問題的最佳解組合而成。若組合時必須回頭修改子問題的選擇，DP 的轉移式就不成立。
- 重疊子問題：遞迴展開後，同一組參數會被問到很多次。若子問題都不重複，把答案存起來沒有好處，那是分治或單純遞迴。
缺第一個，表格填的是錯的。缺第二個，表格只是把遞迴寫成迴圈，複雜度不會更好。
3. 四步設計法
拿到一題，依這個順序寫，不要先寫程式。
- 狀態。一句話：
dp[i]或dp[i][j]代表什麼。參數要夠描述「剩下的問題」，又不要多到狀態數爆炸。 - 轉移。
dp[...]由哪些更小的狀態、用什麼運算（min / max / 加總）得到。寫出為什麼每個候選都合法。 - 基底。最小的狀態是什麼，答案是多少。很多 bug 出在這裡，而不是轉移。
- 計算順序。自底向上時，用到的狀態必須已經算完。拓撲順序錯了，讀到的是初值。
複雜度通常是
[ O(\text{狀態數} \times \text{每個狀態的轉移代價}) ]
4. 自頂向下與自底向上
自頂向下（備忘錄）：照遞迴寫，第一次算到就存進表，之後直接回傳。優點是只算「真的會走到」的狀態。缺點是遞迴深度可能爆堆疊，常數也較大。
自底向上：迴圈依順序填表。優點是空間與順序可控，方便滾動陣列。缺點是會填到用不到的狀態。
兩者答案相同。教學時先寫遞迴確認轉移，再改成迴圈。
5. 範例：硬幣找零
面額 coins = {1, 3, 4}，湊出金額 6，求最少硬幣數。每種面額無限個。
狀態：dp[x] = 湊出金額 x 的最少硬幣數。
轉移：
[ dp[x] = \min_{c \le x} \bigl(dp[x-c] + 1\bigr) ]
基底：dp[0] = 0。其餘先設成一個哨兵（比任何合理答案大，例如 x+1）。
手算：
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| dp | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
dp[6]：1+dp[5]=3，1+dp[3]=2，1+dp[2]=3，最小值 2。一組方案是 3+3 或 4+1+1，枚數都是 2。
若沒有面額 1，而且湊不出來，dp[x] 會停在哨兵。回傳前要檢查，不要把哨兵當答案。
時間 (O(n \cdot |coins|))，空間 (O(n))。
6. 範例：最長遞增子序列
序列 a = [3, 1, 4, 1, 5, 9, 2, 6]，求最長嚴格遞增子序列的長度（不必連續）。
狀態：dp[i] = 以 a[i] 結尾的最長遞增子序列長度。
轉移：
[ dp[i] = 1 + \max{ dp[j] : j < i,\ a[j] < a[i] } ]
沒有這樣的 j 時，長度就是 1。
手算（只列會更新的決策）：
| i | a[i] | dp[i] | 接到誰 |
|---|---|---|---|
| 0 | 3 | 1 | — |
| 1 | 1 | 1 | — |
| 2 | 4 | 2 | 3 或 1 |
| 3 | 1 | 1 | — |
| 4 | 5 | 3 | 4 |
| 5 | 9 | 4 | 5 |
| 6 | 2 | 2 | 1 |
| 7 | 6 | 4 | 5 |
答案是 max dp[i] = 4，例如 1,4,5,9 或 1,4,5,6。
這個寫法 (O(n^2))。若只需要長度，維護「長度為 k 的遞增子序列的最小結尾」，對這個結尾陣列做二分，可到 (O(n\log n))。那個結尾陣列不是子序列本身，還原方案要另外記前驅。二分搜尋的寫法見 Binary_Search_Teaching_Materials.md。
7. 範例：矩陣鏈相乘
矩陣鏈 (A_1 A_2 A_3)，維度依序是 (2\times 3)、(3\times 4)、(4\times 2)。乘法結合律成立，但標量乘法次數不同。
- ((A_1 A_2)A_3)：(A_1 A_2) 花 (2\cdot 3\cdot 4 = 24)，結果 (2\times 4) 再乘 (A_3) 花 (2\cdot 4\cdot 2 = 16)，合計 40。
- (A_1(A_2 A_3))：(A_2 A_3) 花 (3\cdot 4\cdot 2 = 24)，結果 (3\times 2) 再乘 (A_1) 花 (2\cdot 3\cdot 2 = 12)，合計 36。
最佳是 36。
狀態：dp[i][j] = 只乘第 i 到第 j 個矩陣（1-based）的最少標量乘法次數。令維度陣列 d = [2, 3, 4, 2]，第 k 個矩陣是 d[k-1] × d[k]。
轉移：在 i..j 之間選切開點 k
[ dp[i][j] = \min_{i \le k < j} \bigl(dp[i][k] + dp[k+1][j] + d[i-1]\cdot d[k]\cdot d[j]\bigr) ]
基底：dp[i][i] = 0（單一矩陣不用乘）。
順序：區間長度由短到長。長度 2 算完才能算長度 3。這就是區間 DP。
本例 dp[1][3] = 36，切開點在第 1 個矩陣之後。
時間 (O(n^3))，空間 (O(n^2))。
8. 狀態設計目錄
看到題目外形，先猜狀態長什麼樣子，再驗證最佳子結構。
| 外形 | 常見狀態 | 本站已有的例子 |
|---|---|---|
| 一條序列，決定每個位置 | dp[i]：只看前 i 個 |
硬幣、爬階、最大子段和（分析教材的 Kadane 是它的貪心特例） |
| 序列 + 每個元素拿或不拿，容量有限 | dp[i][w] |
02_Knapsack_Teaching_Materials.tex |
| 布林可達 | dp[x] = 能否湊出 x |
03_SubsetSum_Partition_Teaching_Materials.tex |
| 兩條序列對齊 | dp[i][j] |
編輯距離、LCS（模糊搜尋教材） |
| 區間合併 | dp[i][j]，依長度填 |
矩陣鏈、戳破氣球一類 |
| 樹上，子樹獨立 | dp[u][選/不選] |
需要先有樹的 DFS |
| 集合很小，(n \le 20) | dp[S][v]，S 是位元遮罩 |
08_HamiltonianPath_Teaching_Materials.tex |
位元 DP 的狀態數是 (O(2^n \cdot n))，轉移若再掃一次集合外的點，就是 (O(2^n \cdot n^2))。(n) 到 22 左右就該停，這不是實作不優，是狀態數本身。
9. 空間滾動
若 dp[i] 只依賴 dp[i-1]，兩個陣列輪流寫即可，空間從 (O(nW)) 降到 (O(W))。0/1 背包必須由右往左更新那一列，否則同一個物品會被用兩次。完全背包（物品無限）才由左往右。這個方向在背包教材的「一維空間優化」有對應程式，方向搞反是最常見的錯誤。
區間 DP 不能滾動掉整張表，因為長區間同時依賴很多短區間。
10. 還原一個最佳方案
表格通常只存「最佳值」。若要印出選了哪些硬幣、切在哪：
- 多存
prev[x]：湊出x時最後選的硬幣。 - 或從
dp[n]往回，看哪個轉移真的取到最小值。
往回時要用和填表同一個轉移式。填表用 min、還原時改用另一個條件，會得到對不上的方案。
11. 什麼時候不該用 DP
- 子問題不重疊：合併排序、快速排序，用分治。
- 沒有最佳子結構：0/1 背包若改成「物品之間有任意排斥、不能寫成容量裡的局部決策」，轉移就斷了。此時可能是圖搜尋、回溯，或根本是 NP-hard 而且結構不夠乾淨。
- 只是要一個可接受的解、不要求最佳：見貪心教材與 NP 教材的近似演算法。貪心能證明時，不要先寫 (O(n^2)) 的 DP。
- 狀態裡藏了整個排列：那是 (n!)，不是 DP。
12. 常見陷阱
- 狀態定義含糊。 「
dp[i]是前 i 個的答案」和「以 i 結尾的答案」差一個迴圈。LIS 若寫成前者，轉移會不對。 - 哨兵溢出。
INF + 1若INF已是INT_MAX，會溢位變成負數，min 會選到它。用int64，或哨兵設成一個不會再加的值。 - 0/1 與完全背包的迴圈方向。 見第 9 節。
- 區間 DP 依下標而不是依長度迴圈。
dp[i][j]可能讀到還沒算的dp[i][k]。 - 把「能湊出」和「最少個數」寫在同一格卻沒初始化。 布林 DP 的 false 和整數 DP 的 0 意義不同。
- 負面額或負權。 上面的硬幣轉移假設面額為正。負數會讓子問題不「變小」，順序不存在，甚至有無限迴圈。
13. 練習題
- 面額
{2, 5}，金額3。dp陣列應該長什麼樣？函式該回傳什麼？ - 寫出「爬樓梯，每次 1 或 2 階，到第 n 階的方法數」的狀態、轉移、基底。它和費氏數列是什麼關係？
- 0/1 背包容量 6，物品
(w,v) = (2,3), (3,4), (4,5)。最大價值是多少？若一維陣列由左往右更新，重量 2 的物品為什麼可能被算成價值 9？ - 矩陣維度
d = [2, 3, 4, 2]已在第 7 節算過。把dp[1][2]、dp[2][3]、dp[1][3]都寫出來。 - 為什麼「印出 LIS 本體」不能只靠 (O(n\log n)) 那個最小結尾陣列？
參考答案
dp[0]=0，dp[1]與dp[3]維持哨兵（凑不出），dp[2]=1。金額 3 應回傳「不可能」，而不是哨兵數字。dp[n] = dp[n-1] + dp[n-2]，dp[0]=1（停在地面一種方式）或依定義改成dp[1]=1, dp[2]=2。方法數是費氏數列，只是編號平移。- 0/1 最佳是 8：第一件與第三件（重量 6、價值 8）。由左往右更新時，重量 2 的物品可以在同一輪被重複使用三次，湊出重量 6、價值 9，這對 0/1 是非法的。正確的一維更新必須由右往左。
dp[1][2] = 2*3*4 = 24，dp[2][3] = 3*4*2 = 24，dp[1][3] = min(24+0+2*4*2,\ 0+24+2*3*2) = min(40, 36) = 36。- 最小結尾陣列的第 k 格是「長度 k 的某個子序列的結尾」，這些結尾不一定來自同一條子序列，也不能代表當時的前一個元素。要還原必須在 (O(n^2)) 表上記前驅，或在二分版本額外存前驅索引。
小結
DP 是把有重疊、有最佳子結構的遞迴，改成每個狀態只算一次。設計順序永遠是：狀態一句話、轉移、基底、填表順序。複雜度是狀態數乘上轉移代價。背包、編輯距離、區間合併、位元遮罩是同一套骨架；差別只在狀態的參數。沒有最佳子結構就不要填表。