E1: 終極挑戰：動態規劃與最佳化

你已經完成了從月球到冥王星的漫長旅程！現在面臨最終挑戰：資源最佳化問題。在太空探險中，資源（燃料、氧氣、時間）都極其寶貴，你需要找到「最優解」而不僅僅是「可行解」。

動態規劃（Dynamic Programming, DP）是解決最佳化問題的終極武器。它的核心思想是：

• 記住過去：避免重複計算
• 從小到大：用小問題的解構建大問題的解

什麼是動態規劃？

動態規劃適用於具有以下特性的問題：

1. 最優子結構：大問題的最優解包含小問題的最優解
2. 重疊子問題：相同的子問題會被多次計算

DP 的兩種方法

1. Top-Down（記憶化遞迴）

memo = {}
def dp(n):
    if n in memo:
        return memo[n]
    
    # 計算
    result = ...
    memo[n] = result
    return result

2. Bottom-Up（迭代填表）

dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
    dp[i] = ...  # 根據之前的值計算

經典 DP 問題類型

1. 計數型：有多少種方法？
2. 最優化：最大/最小值是多少？
3. 存在性：是否可能？
4. 路徑問題：最佳路徑是什麼？

範例 1：爬樓梯（入門 DP）

import sys
def climb_stairs(n):
    """
    爬 n 階樓梯，每次可以爬 1 或 2 階
    問：有多少種爬法？
    """
    if n <= 2:
        return n
    
    # dp[i] = 爬到第 i 階的方法數
    dp = [0] * (n + 1)
    dp[1] = 1  # 1 階：1 種方法
    dp[2] = 2  # 2 階：2 種方法（1+1 或 2）
    
    for i in range(3, n + 1):
        # 可以從第 i-1 階爬 1 階，或從第 i-2 階爬 2 階
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]
# 任務：計算登上太空站的方法數
n = int(sys.stdin.readline())
result = climb_stairs(n)
print(f"登上 {n} 階太空站的方法數：{result}")

範例 2：背包問題（經典 DP）

import sys
def knapsack(weights, values, capacity):
    """
    0/1 背包問題：每個物品只能選一次
    weights: 物品重量列表
    values: 物品價值列表
    capacity: 背包容量
    返回：最大價值
    """
    n = len(weights)
    
    # dp[i][w] = 前 i 個物品，容量為 w 時的最大價值
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 選擇 1：不拿第 i 個物品
            dp[i][w] = dp[i-1][w]
            
            # 選擇 2：拿第 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 = []
print("可用儀器：")
for i in range(n):
    w, v = map(int, sys.stdin.readline().strip().split())
    weights.append(w)
    values.append(v)
    print(f"儀器 {i+1}: 重量 {w} kg, 價值 {v}")
max_value = knapsack(weights, values, capacity)
print(f"\n載重限制：{capacity} kg")
print(f"最大總價值：{max_value}")

範例 3：最長遞增子序列（LIS）

import sys
def longest_increasing_subsequence(arr):
    """
    找出最長遞增子序列的長度
    """
    if not arr:
        return 0
    
    n = len(arr)
    # dp[i] = 以 arr[i] 結尾的最長遞增子序列長度
    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)
def lis_with_path(arr):
    """返回 LIS 長度和實際序列"""
    if not arr:
        return 0, []
    
    n = len(arr)
    dp = [1] * n
    parent = [-1] * n  # 記錄前一個元素的索引
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j
    
    # 找出最長序列的結尾
    max_length = max(dp)
    max_idx = dp.index(max_length)
    
    # 重建路徑
    path = []
    idx = max_idx
    while idx != -1:
        path.append(arr[idx])
        idx = parent[idx]
    
    path.reverse()
    return max_length, path
# 任務：找出能量讀數的最長上升趨勢
n = int(sys.stdin.readline())
readings = list(map(int, sys.stdin.readline().strip().split()))
length, sequence = lis_with_path(readings)
print(f"能量讀數：{readings}")
print(f"最長上升趨勢長度：{length}")
print(f"趨勢序列：{sequence}")

範例 4：編輯距離（字串 DP）

import sys
def edit_distance(s1, s2):
    """
    計算將 s1 轉換為 s2 的最少操作次數
    操作：插入、刪除、替換
    """
    m, n = len(s1), len(s2)
    
    # dp[i][j] = s1[0:i] 轉換為 s2[0:j] 的最少操作數
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
    # 初始化：空字串的轉換
    for i in range(m + 1):
        dp[i][0] = i  # 刪除 i 個字元
    for j in range(n + 1):
        dp[0][j] = j  # 插入 j 個字元
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                # 字元相同，不需要操作
                dp[i][j] = dp[i-1][j-1]
            else:
                # 三種操作取最小
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # 刪除
                    dp[i][j-1],    # 插入
                    dp[i-1][j-1]   # 替換
                )
    
    return dp[m][n]
# 任務：修正損壞的通訊訊號
original = sys.stdin.readline().strip()
received = sys.stdin.readline().strip()
distance = edit_distance(original, received)
print(f"原始訊號：{original}")
print(f"接收訊號：{received}")
print(f"最少需要 {distance} 次修正")

範例 5：硬幣找零（完全背包）

import sys
def coin_change(coins, amount):
    """
    給定硬幣面額，找出湊成 amount 的最少硬幣數
    每種硬幣可以使用無限次
    """
    # dp[i] = 湊成金額 i 的最少硬幣數
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 金額 0 需要 0 個硬幣
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1
def coin_change_ways(coins, amount):
    """計算有多少種湊法"""
    dp = [0] * (amount + 1)
    dp[0] = 1  # 湊成 0 有 1 種方法（不選）
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]
# 任務：使用能量晶體為太空船充能
n = int(sys.stdin.readline())  # 晶體種類
coins = list(map(int, sys.stdin.readline().strip().split()))
amount = int(sys.stdin.readline())  # 需要的能量
min_crystals = coin_change(coins, amount)
ways = coin_change_ways(coins, amount)
print(f"晶體面額：{coins}")
print(f"需要能量：{amount}")
if min_crystals != -1:
    print(f"最少需要 {min_crystals} 個晶體")
    print(f"共有 {ways} 種組合方式")
else:
    print("無法湊成所需能量！")

關鍵技術點

1. 狀態定義
2. DP 最難的部分：定義 dp[i] 或 dp[i][j] 代表什麼
3. 好的狀態定義讓轉移方程式變簡單

1. 狀態轉移方程

   # 爬樓梯
   dp[i] = dp[i-1] + dp[i-2]
   
   # 背包
   dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight] + value)
   
   # LIS
   dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
   

1. 初始化

   # 基礎情況必須正確
   dp[0] = 0  # 或 1，取決於問題
   

1. 空間優化

   # 如果只需要前一行的數據，可以用滾動陣列
   # 將 O(N²) 空間優化為 O(N)