[Algorithm] 動態規劃

演算法概念

從費氏數列看起

純遞迴算 $F(n) = F(n-1) + F(n-2)$ 會展成指數大的樹——$F(10)$ 就重複算 $F(5)$ 好幾次、$F(3)$ 數十次。每個小問題都從頭算一遍，蠢得很。

動態規劃（DP）就是來解這種「子問題重複出現」的：

把每個子問題算一次，答案記起來，之後直接查表。

費氏數列改 DP：從 $F(0), F(1)$ 開始，由小往大填到 $F(n)$，每格只算一次。複雜度 $O(2^n) \to O(n)$。

什麼時候能用 DP？

兩個條件缺一不可：

1. 最佳子結構：大問題的最佳解，可以用子問題的最佳解組合出來。
2. 重疊子問題：同一個子問題在遞迴中會被用到多次。

沒重疊用分治；沒最佳子結構只能暴搜。

寫 DP 的五步驟

1. 定義狀態：$\text{dp}[i]$ 代表什麼？要能對應到原問題。
2. 寫轉移方程：$\text{dp}[i]$ 怎麼由更小的 $\text{dp}[?]$ 算出來？
3. 找邊界：最小的 case 是什麼？
4. 決定填表順序：要保證用到的子問題已經算好。
5. 找答案位置：最終答案在表的哪一格？

實作風格：

• Top-down（遞迴 + 快取）：直觀，容易從定義照寫
• Bottom-up（從小填到大）：通常更省記憶體、可壓縮維度

以下範例多用 bottom-up。

各適用情境

DAG 最短路徑

白話版

有向無環圖（DAG，沒有環的有向圖）找最短路徑——這是 DP 最乾淨的舞台。

要算「從起點 $s$ 到 $v$ 的最短距離」，先想最後一步：v 的所有入邊 $u \to v$ 中，挑一條讓總長最短的。

直覺：「先到 v 的某個前一站 u，再走 $u \to v$ 那條邊」。試遍所有可能的 u，取最短。

邊界：$\text{dist}(s) = 0$（自己到自己）、其他 $\infty$。

順序問題：算 $\text{dist}(v)$ 要用到 $\text{dist}(u)$。怎麼保證 u 已經算好？→ 用拓樸順序。

複雜度

拓樸排序 $O(V + E)$、掃每條邊一次 $O(V + E)$。總共 $O(V + E)$。每條邊只看一次——拓樸順序保證之後不會再被縮短。

範例

5 節點 A–E，邊：

起點 $s = A$，拓樸序 $A, B, C, D, E$。按順序算：

from collections import defaultdict, deque


def dag_shortest_path(V, edges, s):
    graph = defaultdict(list)
    in_deg = {v: 0 for v in V}
    for u, v, w in edges:
        graph[u].append((v, w))
        in_deg[v] += 1

    order = []
    queue = deque([v for v in V if in_deg[v] == 0])
    while queue:
        u = queue.popleft()
        order.append(u)
        for v, _ in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)

    dist = {v: float('inf') for v in V}
    dist[s] = 0
    for u in order:
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

多階圖

白話版

多階圖（Multistage Graph）是 DAG 的特例：節點分成 $k$ 個 stage，邊只從 stage $i$ 連到 stage $i+1$。像是流水線、時間步規劃。

因為 stage 是天然的拓樸順序，可以直接從終點往回推（backward DP）：

意思：「在 v，要往下一站走，哪條路加上之後到終點的距離最短？」

邊界 $f(t) = 0$。從 stage $k$ 往前推到 stage 1。

複雜度

每條邊看一次 $O(V + E)$。空間可壓到 $O(n_{\max})$（單一 stage 最大節點數）——只要保留下一個 stage 的 $f$ 值。

範例

7 節點分 4 個 stage：

邊：

從 stage 4 往回：

最短路徑長度 7，路徑 $s \to A \to D \to t$。

def multistage_shortest(stages, edges):
    # stages: list of lists, stages[0]=[s], stages[-1]=[t]
    graph = {}
    for u, v, w in edges:
        graph.setdefault(u, []).append((v, w))

    t = stages[-1][0]
    f = {t: 0}
    for stage in reversed(stages[:-1]):
        for v in stage:
            f[v] = min(w + f[u] for u, w in graph.get(v, []))
    return f[stages[0][0]]

最長遞增子數列（LIS）

白話版

給整數序列，找最長的「遞增子數列」——不必連續、順序不變。

例：序列 $[3, 1, 4, 1, 5, 9, 2, 6]$ 的一個遞增子數列是 $[1, 4, 5, 9]$，長度 4。

關鍵狀態：「以 $a[i]$ 結尾的最長遞增子數列長度」叫做 $\text{dp}[i]$。「以 $a[i]$ 結尾」這個限定很重要，否則轉移很難寫。

轉移：在 $a[i]$ 之前找一個 $a[j]$（$j < i$ 且 $a[j] < a[i]$，也就是它可以接在 $a[j]$ 後面繼續遞增），挑最長的接下去：

沒這種 $j$ 就 $\text{dp}[i] = 1$（自己一個）。答案 $\max(\text{dp})$。

複雜度

樸素 DP：每個 $i$ 掃前面所有 $j$ → $O(n^2)$。

進階版用 patience sorting（DP + 二分搜）可壓到 $O(n \log n)$：維護遞增陣列 tails，每個新元素二分找第一個 $\geq$ 它的位置覆蓋掉（沒有就 append）。最後 tails 長度就是答案。

範例

$a = [3, 1, 4, 1, 5, 9, 2, 6]$（嚴格版）：

$\text{dp} = [1, 1, 2, 1, 3, 4, 2, 4]$，答案 $= 4$，對應 $[1, 4, 5, 9]$。

def lis_n2(arr):
    dp = [1] * len(arr)
    for i in range(len(arr)):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0


from bisect import bisect_left


def lis_nlogn(arr):
    tails = []
    for x in arr:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

最長共同子序列（LCS）

白話版

「子序列」= 從字串挑出一些字元（順序不變、可以跳過），組成的新字串。例如 ABCDE 的子序列可以是 ACE、BD、空字串等等，但 EA 不是（順序錯了）。

給兩字串 $X$、$Y$，LCS 就是最長、同時是兩者子序列的字串。

例：$X =$ AGCAT、$Y =$ GAC。共同子序列有 A、AC、GA 等等，最長是 AC 或 GA，長度 2。

實務應用：DNA 比對（兩物種同源程度）、diff / git 差異比對、編輯距離。

轉移方程

狀態 $\text{dp}[i][j]$ = $X$ 取前 $i$ 個字元、$Y$ 取前 $j$ 個字元的 LCS 長度。

Case 1：末字元相同（$X[i-1] = Y[j-1]$，注意是 0-indexed）

這個字元一定能進 LCS → 答案 = 「再退一步的 LCS」+ 1：

Case 2：末字元不同

至少要丟掉其中一個結尾字元，看哪邊丟掉後 LCS 較長：

邊界 $\text{dp}[0][j] = \text{dp}[i][0] = 0$（空字串的 LCS 是空）。

複雜度

填 $(m+1)(n+1)$ 表、每格 $O(1)$ → $O(mn)$。空間 $O(mn)$，若只要長度可壓到 $O(\min(m, n))$。

範例

$X =$ AGCAT、$Y =$ GAC：

幾格細節：

• $(1, 2)$：$X[0] =$ A 對上 $Y[1] =$ A → $\text{dp}[0][1] + 1 = 1$
• $(3, 3)$：$X[2] =$ C 對上 $Y[2] =$ C → $\text{dp}[2][2] + 1 = 2$
• $(4, 2)$：$X[3] =$ A 對上 $Y[1] =$ A → $\text{dp}[3][1] + 1 = 2$

答案 $\text{dp}[5][3] = 2$。

還原 LCS：從右下 $(m, n)$ 往左上走——遇到 $X[i-1] = Y[j-1]$ 走對角 $(-1, -1)$ 並紀錄字元；否則往值較大的那邊（上或左）走。追出 GA 或 AC。

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

一般最短路徑（Bellman-Ford）

白話版

DAG 的拓樸序法在有環圖就行不通了（環會卡死「依賴關係」）。Bellman-Ford 處理有環、甚至含負權邊的一般圖。

正權邊用 Dijkstra 更快；這邊聚焦能處理負邊的 Bellman-Ford。

維護一張表 $\text{dist}[v]$ = 從起點 $s$ 到 $v$目前已知的最短距離。對每條邊 $u \to v$（權重 $w$）做檢查：

白話：「經過 u 再走這條邊到 v，比現在的記錄還短嗎？若是，就改寫」。

把所有邊都檢查一次叫一輪。重複跑直到沒任何邊能再縮短（最多 $|V| - 1$ 輪保證收斂）。

這個「檢查並縮短」的動作，教科書叫 relax（鬆弛），但名字滿誤導的、不必糾結。實際就是上面那個 if 條件。

為什麼 Dijkstra 不行？ Dijkstra 每輪挑「目前 dist 最小的」當「已確定」、之後不改。但有負邊時，已確定的點可能還能被「繞遠路後減扣」變更短——這個假設破掉了。Bellman-Ford 因為「每輪所有邊都重檢查」抓得到這種修正。

DP 視角

正式的 DP 狀態：$\text{dist}_k(v)$ = 從 $s$ 到 $v$、最多使用 $k$ 條邊的最短距離。轉移：

任何不含環的最短路徑最多 $|V| - 1$ 條邊 → 跑 $|V| - 1$ 輪保證收斂。實作上不用真的開二維表，每輪就用同一張 $\text{dist}$ 更新即可。

偵測負權環：跑完 $|V| - 1$ 輪後再跑一輪，若還能縮短就有可達的負權環。

複雜度

每輪掃 $E$ 條邊、$V - 1$ 輪 → $O(V \cdot E)$。比 Dijkstra（$O((V + E) \log V)$）慢，但能處理負權邊。

範例

5 節點，含負權邊：

起點 $s = A$。跑 4 輪（$|V| - 1$）：

最終 $A = 0, B = 2, C = 7, D = 4, E = -2$。

def bellman_ford(V, edges, s):
    dist = {v: float('inf') for v in V}
    dist[s] = 0
    for _ in range(len(V) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError('negative cycle')
    return dist

所有節點對最短路徑（Floyd-Warshall）

白話版

要一次算出所有節點對之間的最短路徑。跑 $V$ 次 Bellman-Ford 是 $O(V^2 E)$ 很貴；Floyd-Warshall 用不同的 DP 維度，$O(V^3)$ 一次解掉。

巧妙觀察：「從 $i$ 到 $j$ 的最短路徑，要嘛經過某個中繼點 $k$，要嘛不經過。」

逐步把中繼點集合放寬。狀態 $\text{dp}_k[i][j]$ = 從 $i$ 到 $j$、只允許用編號 $\leq k$ 的節點當中繼的最短距離。轉移：

兩個選擇：

• 不走 $k$：維持原本 $\text{dp}_{k-1}[i][j]$
• 走 $k$：$i \to k$ 加上 $k \to j$

取兩者較小。

複雜度

三層迴圈各 $V$ 次 → $O(V^3)$。空間 $O(V^2)$。適合稠密圖；稀疏圖（$E \ll V^2$）跑 $V$ 次 Dijkstra 可能更快。

範例

4 節點（0–3），初始直接邊權重：

$k = 0$（允許經過 0）：$(1, 3): 8 + 7 = 15$、$(2, 1): 5 + 3 = 8$、$(3, 1): 2 + 3 = 5$。

$k = 1$（再允許經過 1）：$(0, 2): 3 + 2 = 5$、$(3, 2): 5 + 2 = 7$。

$k = 2$（再允許經過 2）：$(0, 3): 5 + 1 = 6 < 7$、$(1, 3): 2 + 1 = 3 < 15$。

$k = 3$（再允許經過 3）：$(1, 0): 3 + 2 = 5 < 8$、$(2, 0): 1 + 2 = 3 < 5$、$(2, 1): 1 + 5 = 6 < 8$。

最終矩陣。

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF] * V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

0/1 背包

白話版

$n$ 件物品，第 $i$ 件重 $w_i$、價值 $v_i$。背包容量 $W$。每件物品只能拿或不拿（不能切、不能多拿）。最大化總價值。

對每件物品都只有兩個選擇：拿 或 不拿。問題拆成「處理完第 $i$ 件、剩 $w$ 容量時的最大價值」就能 DP。

狀態 $\text{dp}[i][w]$ = 只考慮前 $i$ 件、背包容量 $w$ 時的最大價值。轉移：

• $w_i > w$（裝不下，只能不拿）：$\text{dp}[i][w] = \text{dp}[i-1][w]$
• 否則拿或不拿取較大：$\text{dp}[i][w] = \max\bigl(\text{dp}[i-1][w],\; \text{dp}[i-1][w - w_i] + v_i\bigr)$

直覺：對第 $i$ 件物品，「不拿」就是前 $i-1$ 件在 $w$ 容量下的最大值；「拿」就是先騰出 $w_i$ 的位置（前 $i-1$ 件用剩下 $w - w_i$）再加上 $v_i$。

複雜度

填 $n \cdot (W + 1)$ 表 → $O(nW)$。空間壓縮到 $O(W)$（只需上一列）。

範例

$W = 10$，5 件物品：

填表：

幾格細節：

• $(2, 5)$：物品 2 重 3。不拿 $= 3$、拿 $= \text{dp}[1][2] + 4 = 3 + 4 = 7$。取 7。
• $(3, 9)$：物品 3 重 4。不拿 $= 7$、拿 $= \text{dp}[2][5] + 5 = 7 + 5 = 12$。取 12。
• $(5, 10)$：物品 5 重 9。不拿 $= 13$、拿 $= \text{dp}[4][1] + 10 = 0 + 10 = 10$。取 13。

最大總價值 13。

還原物品：從 $(5, 10)$ 往回——

• $(5, 10) = 13 = \text{dp}[4][10]$ → 物品 5 沒拿
• $(4, 10) = 13 \neq \text{dp}[3][10] = 12$ → 物品 4 有拿，移到 $(3, 5)$
• $(3, 5) = 7 = \text{dp}[2][5]$ → 物品 3 沒拿
• $(2, 5) = 7 \neq \text{dp}[1][5] = 3$ → 物品 2 有拿，移到 $(1, 2)$
• $(1, 2) = 3 \neq \text{dp}[0][2] = 0$ → 物品 1 有拿

拿物品 1、2、4，重 $2 + 3 + 5 = 10$，價值 $3 + 4 + 6 = 13$ ✓

def knapsack_01(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for j in range(W, w - 1, -1):  # 反向！避免同物品被拿多次
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

常見考法

複雜度推導：

• Bellman-Ford $O(VE)$：$V - 1$ 輪 × 每輪 $E$ 條邊
• Floyd-Warshall $O(V^3)$：三層迴圈各 $V$ 次
• LCS $O(mn)$：$(m+1)(n+1)$ 表、每格 $O(1)$
• LIS $O(n^2)$：$\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$；patience 可降 $O(n \log n)$
• 0/1 Knapsack $O(nW)$：$n \cdot (W+1)$ 表

下一篇 NP 完備理論——即使 Knapsack 有 DP 解，也逃不過「問題本身就難」的宿命。