Terry Yao's Blog

algorithms進階 DP：當狀態不再是一個數字
algorithms

進階 DP：當狀態不再是一個數字

閱讀時間約 9 分鐘

基礎 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

Tree DP：狀態長在子樹上

前面的狀態都是陣列的一段，Tree DP 換成「以某個節點為根的子樹」。經典題是最大權重獨立集：在一棵樹上挑節點，被挑的兩兩不相鄰，讓權重和最大。

難點還是狀態——這裡一個節點要記兩種可能：

dp[v][0] = 不選 v 時，v 這棵子樹能拿到的最大權重
dp[v][1] = 選了 v 時，v 這棵子樹能拿到的最大權重
 
dp[v][0] = Σ max(dp[u][0], dp[u][1])   // v 不選，小孩選不選都行
dp[v][1] = weight[v] + Σ dp[u][0]      // v 選了，小孩一律不能選

轉移就一句話：選了自己，小孩全禁；不選自己，小孩自由發揮。剩下的交給一次 DFS 由葉往根回填：

void dfs(int v, int parent) {
    dp[v][1] = weight[v];   // 選 v，先計自身
    dp[v][0] = 0;           // 不選 v
    for (int u : adj.get(v)) {
        if (u == parent) continue;      // 別走回父節點
        dfs(u, v);
        dp[v][0] += Math.max(dp[u][0], dp[u][1]);
        dp[v][1] += dp[u][0];
    }
}
// 答案：max(dp[root][0], dp[root][1])

O(n) 就掃完整棵樹。公司組織架構辦尾牙、不想讓直屬上下級同桌尷尬，要最大化「歡樂值」——本質就是這題。

Digit DP：一位一位地數

「1 到 n 之間，各位數字和等於 k 的數有幾個？」n 可以大到 10^18，一個一個數是死路。Digit DP 的招式是把數字拆成一位一位填，狀態裡藏一個很不直覺的旗標：tight。

狀態：(pos, sum, tight)
  pos   = 現在填第幾位
  sum   = 已填位數的數字和
  tight = 前面每一位是否都貼著上界 n
 
tight = true ：這一位最多只能填到 n 對應位的數字（不然就爆過 n）
tight = false：前面已經「小於」n 了，這一位 0~9 隨便填

tight 就是這題狀態定義的靈魂——沒有它，你沒辦法一邊逐位填、一邊保證不超過上界：

long dfs(String num, int pos, int sum, boolean tight, int target, long[][][] memo) {
    if (sum > target) return 0;                         // 剪枝
    if (pos == num.length()) return sum == target ? 1 : 0;
    int t = tight ? 1 : 0;
    if (memo[pos][sum][t] != -1) return memo[pos][sum][t];
 
    int limit = tight ? num.charAt(pos) - '0' : 9;      // tight 才卡上界
    long count = 0;
    for (int d = 0; d <= limit; d++) {
        count += dfs(num, pos + 1, sum + d, tight && d == limit, target, memo);
    }
    return memo[pos][sum][t] = count;
}

一旦某位填得比上界小，tight 就永遠 false 下去，後面整段可以放心用 memo 共用——不同的 n 只要開頭那條「貼邊」的路徑不同而已。

這幾類 DP 的狀態長什麼樣

類型狀態的形狀代表題
線性 DPdp[i]：處理到第 i 個LIS、背包、爬樓梯
二維 DPdp[i][j]：兩個序列的位置LCS、Edit Distance
區間 DPdp[i][j]：一段 [i,j] 區間矩陣鏈、戳氣球、回文分割
Bitmask DPdp[mask][v]：子集 + 落點TSP、集合覆蓋
Tree DPdp[v][狀態]：子樹 + 選擇最大獨立集、樹上背包
Digit DPdp[pos][特徵][tight]：填到第幾位統計符合條件的數

看得出來越往下走，狀態越不像「一個數字的索引」，而是「一個結構的描述」——這正是進階 DP 真正難的地方。

🎬 互動視覺化：進階 DP 的狀態怎麼展開 — Edit Distance 的二維表、區間 DP 由小區間拼出大區間、Bitmask 逐一點亮已訪問的城市，看不同形狀的狀態各自怎麼被填滿。

進階 DP 很少卡在轉移方程式——通常卡在「原來狀態要這樣定義」這一步。

接下來往哪走

關係圖譜

反向連結