D2: 優化的藝術：動態規劃 (DP)

在冥王星邊界，資源極度稀缺。每個決策都必須是最優的，沒有試錯的餘地。動態規劃（Dynamic Programming, DP）是解決優化問題的終極武器。

• 識別問題是否適合用 DP 解決
• 定義狀態和轉移方程
• 實現高效的 DP 解法

DP 是 APCS 5 級分的核心技能，也是最具挑戰性的演算法之一。

什麼是動態規劃？

1. 最優子結構（Optimal Substructure）
2. 問題的最優解可由子問題的最優解構造出來

1. 重疊子問題（Overlapping Subproblems）
2. 遞迴求解時，相同的子問題會被重複計算多次

經典範例：費氏數列

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)  # 大量重複計算

def fib_dp(n):
    if n <= 1:
        return n
    
    memo = {}
    memo[0] = 0
    memo[1] = 1
    
    for i in range(2, n+1):
        memo[i] = memo[i-1] + memo[i-2]
    
    return memo[n]

DP 的兩種實現方式

#### 1. Top-Down（由上而下）+ Memoization

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]  # 已計算過，直接回傳
    
    if n <= 1:
        return n
    
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

• 思路自然，接近遞迴思維
• Python 有 @lru_cache 裝飾器可自動實現

• 可能遇到遞迴深度限制

#### 2. Bottom-Up（由下而上）+ Tabulation

def fib_table(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

• 避免遞迴開銷
• 更容易優化空間複雜度

• 需要仔細設計迭代順序

DP 解題步驟

1. 定義狀態：dp[i] 代表什麼？
2. 找出轉移方程：dp[i] 如何從之前的狀態計算？
3. 確定初始條件：dp[0], dp[1] 等基礎情況
4. 確定計算順序：從小到大還是從大到小？
5. 確定答案位置：最終答案在 dp[?]

範例 1：爬樓梯問題

import sys
def climb_stairs(n):
    """
    爬 n 階樓梯，每次可爬 1 或 2 階
    問有多少種爬法？
    
    狀態定義：dp[i] = 爬到第 i 階的方法數
    轉移方程：dp[i] = dp[i-1] + dp[i-2]
    """
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1  # 爬 1 階：1 種方法
    dp[2] = 2  # 爬 2 階：2 種方法 (1+1 或 2)
    
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]
# 主程式
n = int(sys.stdin.readline())
print(f"爬 {n} 階樓梯有 {climb_stairs(n)} 種方法")

範例 2：最小路徑和

import sys
def min_path_sum(grid):
    """
    從左上角走到右下角，只能向右或向下
    找出路徑和最小的路徑
    
    狀態定義：dp[i][j] = 到達 (i,j) 的最小路徑和
    轉移方程：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    """
    rows = len(grid)
    cols = len(grid[0])
    
    # 初始化 DP 表
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    
    # 初始化第一行
    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # 初始化第一列
    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # 填充 DP 表
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    return dp[rows-1][cols-1]
# 讀取網格
rows = int(sys.stdin.readline())
cols = int(sys.stdin.readline())
grid = []
for _ in range(rows):
    row = list(map(int, sys.stdin.readline().split()))
    grid.append(row)
result = min_path_sum(grid)
print(f"最小路徑和：{result}")

範例 3：0/1 背包問題

import sys
def knapsack(weights, values, capacity):
    """
    0/1 背包問題：每個物品只能選或不選
    
    狀態定義：dp[i][w] = 前 i 個物品，容量 w 時的最大價值
    轉移方程：
        不選第 i 個：dp[i][w] = dp[i-1][w]
        選第 i 個：dp[i][w] = dp[i-1][w-weight[i]] + value[i]
        取最大值
    """
    n = len(weights)
    
    # 創建 DP 表
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 不選第 i 個物品
            dp[i][w] = dp[i-1][w]
            
            # 如果能選第 i 個物品
            if w >= weights[i-1]:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
    
    return dp[n][capacity]
# 讀取數據
n = int(sys.stdin.readline())
capacity = int(sys.stdin.readline())
weights = []
values = []
for _ in range(n):
    w, v = map(int, sys.stdin.readline().split())
    weights.append(w)
    values.append(v)
max_value = knapsack(weights, values, capacity)
print(f"最大價值：{max_value}")

範例 4：最長遞增子序列 (LIS)

import sys
def longest_increasing_subsequence(arr):
    """
    找出最長遞增子序列的長度
    
    狀態定義：dp[i] = 以 arr[i] 結尾的最長遞增子序列長度
    轉移方程：dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
    """
    n = len(arr)
    if n == 0:
        return 0
    
    # 初始化：每個元素自己就是長度 1 的子序列
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)
# 主程式
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
lis_length = longest_increasing_subsequence(arr)
print(f"最長遞增子序列長度：{lis_length}")

範例 5：使用 @lru_cache

import sys
from functools import lru_cache
@lru_cache(maxsize=None)
def count_ways(n, k):
    """
    用 k 種顏色塗 n 個柵欄
    相鄰柵欄不能同色
    
    使用 Python 的 lru_cache 自動實現 memoization
    """
    if n == 1:
        return k
    if n == 2:
        return k * k
    
    # 第 n 個柵欄可以：
    # 1. 與第 n-1 個不同色：count_ways(n-1, k) * (k-1)
    # 2. 與第 n-2 個不同色但與 n-1 同色：count_ways(n-2, k) * (k-1)
    return (k - 1) * (count_ways(n-1, k) + count_ways(n-2, k))
# 主程式
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
ways = count_ways(n, k)
print(f"塗色方法數：{ways}")

關鍵技術點

#### 1. 狀態定義的藝術

dp[i] = 到達位置 i 的最優解

dp[i][j] = 考慮前 i 個元素，某個限制為 j 時的最優解

#### 2. 空間優化

許多 DP 只需要前一個或前兩個狀態：

# 原始：O(N) 空間
dp = [0] * n
for i in range(n):
    dp[i] = dp[i-1] + dp[i-2]
# 優化：O(1) 空間
prev2, prev1 = 0, 1
for i in range(2, n+1):
    curr = prev1 + prev2
    prev2, prev1 = prev1, curr

#### 3. DP vs 遞迴

| 特性 | 遞迴 | DP | |------|------|-----| | 時間複雜度 | 指數級 | 多項式級 | | 空間複雜度 | 遞迴堆疊 | DP 表 | | 實現難度 | 簡單直觀 | 需要設計 |