跳轉到

第四部分：系統最佳化（續）

< 上一題：部署順序規劃 | 返回目錄 | 下一題：效能瓶頸分析 >

場景：傳輸成本怎麼最小化？

財務部給了你一個挑戰：

「我們有 1TB 資料要從台北傳到法蘭克福。有多條路線，每條價格不同。怎麼分配才能總成本最低？」

這不是簡單的最短路徑——你可以把資料**拆分**到多條路徑，而且某些路線有**容量限制**。

這是一個**最佳化問題**，需要用 Dynamic Programming（動態規劃） 來解決。

第 9 題：傳輸成本最小化 - Dynamic Programming

(a) DP 的核心思想

3 分 ・ 大二

你需要知道：什麼問題適合用 DP？

題目：

  1. DP 的兩個核心性質是什麼？

  2. 說明「重疊子問題」和「最優子結構」

  3. 比較 DP 和分治法（Divide and Conquer）

解答

1. DP 的核心性質：

  • 最優子結構（Optimal Substructure）：問題的最優解包含子問題的最優解
  • 重疊子問題（Overlapping Subproblems）：同一個子問題被多次用到

2. 解釋：

最優子結構：要解決大問題，只需要「最優地」解決小問題，然後組合。

例：最短路徑。\(s \to t\) 的最短路徑經過 \(v\)，則 \(s \to v\) 的部分也必須是最短的。

重疊子問題：遞迴時，同一個子問題被算很多次。

例：Fibonacci。\(F(n) = F(n-1) + F(n-2)\)，計算 \(F(n)\) 時會多次計算 \(F(k)\)。

3. DP vs 分治：

分治 DP
子問題 不重疊 重疊
方法 遞迴 記憶化 / 制表
例子 Merge Sort, Quick Sort Fibonacci, LCS

分治：子問題獨立，直接遞迴。

DP：子問題重疊，需要「記住」已算過的結果。

(b) 經典問題：0/1 背包

4 分 ・ 大三

你需要知道：如何用 DP 解決有限制的選擇問題？

問題：有 \(n\) 條傳輸路線，第 \(i\) 條能傳 \(w_i\) GB，成本 \(c_i\)。總預算 \(W\) GB，求能達到的最小成本。

等等，這個問題描述有點怪... 讓我重新定義：

背包問題：有 \(n\) 個物品，第 \(i\) 個重量 \(w_i\)，價值 \(v_i\)。背包容量 \(W\)，求能裝的最大價值。

題目：

  1. 定義 DP 狀態和轉移方程

  2. 實現 \(O(nW)\) 的演算法

  3. 優化空間到 \(O(W)\)

解答

1. DP 定義：

\(dp[i][j]\) = 考慮前 \(i\) 個物品，容量為 \(j\) 時的最大價值

轉移：

\[dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)\]
  • 不選第 \(i\) 個：\(dp[i-1][j]\)
  • 選第 \(i\) 個（如果 \(j \geq w_i\)）：\(dp[i-1][j-w_i] + v_i\)

2. 實現：

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(W + 1):
            dp[i][j] = dp[i-1][j]
            if j >= weights[i-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-weights[i-1]] + values[i-1])

    return dp[n][W]

3. 空間優化：

注意 \(dp[i][j]\) 只依賴 \(dp[i-1][...]\)，可以壓縮成一維。

關鍵：\(j\) 要從大到小遍歷，避免覆蓋還沒用到的值。

def knapsack_01_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)

    for i in range(n):
        for j in range(W, weights[i] - 1, -1):  # 從大到小！
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

    return dp[W]

© 經典問題：Longest Common Subsequence (LCS)

4 分 ・ 大三

你需要知道：如何比較兩個序列的相似度？

問題：比較兩個路由器的配置檔，找出**最長公共子序列**。

題目：

  1. 定義 LCS 問題

  2. 寫出 DP 轉移方程

  3. 如何回溯找出實際的 LCS？

解答

1. LCS 問題：

給定序列 \(X = x_1, x_2, ..., x_m\) 和 \(Y = y_1, y_2, ..., y_n\)。

找最長的序列 \(Z\)，使得 \(Z\) 同時是 \(X\) 和 \(Y\) 的子序列。

子序列：可以不連續，但要保持順序。

例：$X = $ "ABCBDAB", $Y = $ "BDCAB"

LCS = "BCAB" 或 "BDAB"，長度 4。

2. DP 轉移：

\(dp[i][j]\) = \(X[1..i]\) 和 \(Y[1..j]\) 的 LCS 長度

\[dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } x_i = y_j \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}\]

3. 回溯：

def lcs_with_backtrack(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])

    # 回溯
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(lcs))

時間複雜度：\(O(mn)\)

(d) 經典問題：矩陣鏈乘法

4 分 ・ 碩一

你需要知道：如何找到最佳的計算順序？

問題：有一連串矩陣相乘 \(A_1 \times A_2 \times ... \times A_n\)，不同的括號方式導致不同的乘法次數。

例：\(A\) (10×30), \(B\) (30×5), \(C\) (5×60)

  • \((AB)C\)：10×30×5 + 10×5×60 = 4500
  • \(A(BC)\)：30×5×60 + 10×30×60 = 27000

題目：

  1. 定義 DP 狀態和轉移

  2. 時間複雜度是多少？

解答

1. DP 定義：

設 \(p_0, p_1, ..., p_n\)，其中 \(A_i\) 是 \(p_{i-1} \times p_i\) 的矩陣。

\(dp[i][j]\) = 計算 \(A_i \times A_{i+1} \times ... \times A_j\) 的最小乘法次數

轉移：

\[dp[i][j] = \min_{i \leq k < j} \{ dp[i][k] + dp[k+1][j] + p_{i-1} \cdot p_k \cdot p_j \}\]

在位置 \(k\) 切開，左半部分結果是 \(p_{i-1} \times p_k\)，右半部分是 \(p_k \times p_j\)，乘起來的成本是 \(p_{i-1} \cdot p_k \cdot p_j\)。

2. 實現：

def matrix_chain_order(p):
    n = len(p) - 1  # 矩陣數量
    dp = [[0] * n for _ in range(n)]

    # 按區間長度遞增
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n-1]

時間複雜度：\(O(n^3)\)

進階挑戰：空間優化技巧總結

3 分 ・ 碩一

你需要知道：DP 的空間如何優化？

解答

常見技巧：

原始空間 優化後 條件
\(O(n \times W)\) \(O(W)\) 每行只依賴上一行
\(O(n \times m)\) \(O(\min(n, m))\) LCS 類型，只需兩行
\(O(n^2)\) \(O(n)\) 某些區間 DP（需要技巧）

0/1 背包：從大到小遍歷，避免同一物品被選多次。

LCS：只保留兩行，交替使用。

滾動陣列：\(dp[i \% 2]\) 取代 \(dp[i]\)。

第 9 題小結：你的最佳化工具箱

「怎麼做決策才能最佳？」
    │
    ├─► (a) DP 的條件？
    │       → 最優子結構 + 重疊子問題
    │
    ├─► (b) 有限選擇？→ 0/1 背包
    │       → dp[i][j] = 前 i 個物品、容量 j
    │       → O(nW)，可壓縮成 O(W)
    │
    ├─► (c) 序列比較？→ LCS
    │       → dp[i][j] = 兩序列前綴的 LCS
    │       → O(mn)
    │
    └─► (d) 計算順序？→ 矩陣鏈乘法
            → 區間 DP
            → O(n³)
問題 狀態 時間 空間
0/1 背包 \(dp[i][W]\) \(O(nW)\) \(O(W)\)
LCS \(dp[m][n]\) \(O(mn)\) \(O(n)\)
矩陣鏈乘 \(dp[n][n]\) \(O(n^3)\) \(O(n^2)\)

< 上一題：部署順序規劃 | 返回目錄 | 下一題：效能瓶頸分析 >