基礎 DP 的挑戰是「找到轉移方程式」；進階 DP 的挑戰是「想到要定義什麼樣的狀態」。
問題升級的關鍵
基礎 DP 的問題，狀態通常是「處理到第 i 個、最優值是多少」——一維的。
進階 DP 的問題開始出現二維狀態（兩個字串的位置）、區間狀態（一段字串）、指數狀態（子集的集合）。這些狀態更難想到，但轉移往往並不複雜。
Edit Distance：量化兩個字串的差距
把 "horse" 改成 "ros" 最少幾步（插入/刪除/替換各算 1 步）？
這是 Levenshtein distance——Git 的 diff 輸出、Google 拼字修正、DNA 序列比對，核心都是這個問題。
狀態：dp[i][j] = 把 s1 的前 i 個字元改成 s2 的前 j 個字元的最少步數
轉移：
s1[i] == s2[j]：dp[i][j] = dp[i-1][j-1]（不需要操作）
s1[i] != s2[j]：dp[i][j] = min(
dp[i-1][j] + 1, // 刪除 s1[i]
dp[i][j-1] + 1, // 插入 s2[j]
dp[i-1][j-1] + 1 // 替換 s1[i] 為 s2[j]
)
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
結果：dp[5][3] = 3 步
區間 DP：矩陣鏈乘法
A(10×30) × B(30×5) × C(5×60) 怎麼加括號算最快？
(A×B)×C：10×30×5 + 10×5×60 = 4,500 次乘法
A×(B×C)：30×5×60 + 10×30×60 = 27,000 次乘法
差了 6 倍。矩陣鏈乘法找最優加括號方案：
dp[i][j] = 矩陣 i 到 j 連乘的最小乘法次數
對所有分割點 k（i ≤ k < j）：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + rows[i] × cols[k] × cols[j])
建表順序：先算長度小的區間，再用它們組合長區間
這類「區間 DP」的標誌是「先處理小區間，再組合大區間」。石子合併、最優括號化、回文分割，都是這個模式。
Bitmask DP：子集的狀態
旅行業務員問題（TSP）：n 個城市各走一遍，求最短路徑。暴力是 O(n!)，n=15 就是 10^12——無法接受。
Bitmask DP 用一個整數表示「哪些城市已訪問」：
dp[mask][v] = 已訪問城市集合為 mask、當前在城市 v 的最短距離
轉移：從 v 走到未訪問的城市 u
dp[mask | (1 << u)][u] = min(dp[mask | (1 << u)][u], dp[mask][v] + dist[v][u])
狀態數：2^n × n；轉移：O(n)
總複雜度：O(2^n × n²)
n=20：2^20 × 400 ≈ 4 億，邊界可接受
Egg Drop：反向定義狀態
k 顆蛋、n 層樓，找臨界樓層最少需要幾次？
直接定義 dp[k][n] = k 顆蛋 n 層樓需要幾次，轉移複雜（每層都是分割點），O(kn²) 太慢。
反向定義：
dp[t][k] = t 次嘗試 + k 顆蛋，能確定的最多樓層數
dp[t][k] = dp[t-1][k-1] + dp[t-1][k] + 1
蛋碎了（往下找） 蛋沒碎（往上找） 當前這層
結果：找最小的 t 使得 dp[t][k] ≥ n
進階 DP 很少卡在轉移方程式——通常卡在「原來狀態要這樣定義」這一步。