DP 核心思想：遞迴 + 記憶化

從費氏數列開始

什麼是動態規劃？

動態規劃（Dynamic Programming, DP） 是將複雜問題分解為重疊的子問題，每個子問題只解一次並儲存結果以備重複使用。

| 方法 | 方向 | 記憶體 | 速度 | |------|------|--------|------| | Top-Down（記憶化） | n → 0 | O(n) call stack | O(n) | | Bottom-Up（表格） | 0 → n | O(n) 陣列 | O(n) |

費氏數列三種實作

from functools import lru_cache

# 遞迴版（O(2ⁿ) — 超慢）
def fib_rec(n):
    if n <= 1: return n
    return fib_rec(n-1) + fib_rec(n-2)

print(f"fib_rec(10) = {fib_rec(10)}")  # 還可以
# print(fib_rec(50))  # 等到天荒地老！

# 方法1：Top-Down 記憶化（O(n) — 超快）
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)

print(f"fib_memo(50) = {fib_memo(50)}")  # 瞬間輸出 12586269025

# 方法2：Bottom-Up 表格法
def fib_tab(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp

fib_table = fib_tab(10)
print(f"fib_tab(10) = {fib_table}")
print(f"fib(10) = {fib_table[10]}")

# 方法3：空間優化 O(1)
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(f"fib_opt(50) = {fib_opt(50)}")

DP 解題三步驟

| 步驟 | 問題 | 費氏數列為例 | |------|------|-------------| | 1. 定義狀態 | dp[i] 代表什麼？ | dp[i] = 第 i 個費氏數列值 | | 2. 遞迴關係 | dp[i] 和前面的關係？ | dp[i] = dp[i-1] + dp[i-2] | | 3. 初始條件 | base case 是什麼？ | dp[0] = 0, dp[1] = 1 |

套用到其他問題

最大子陣列（Kadane 演算法）： | 步驟 | Kadane | |------|--------| | 狀態 | dp[i] = 以位置 i 結尾的最大和 | | 遞迴 | dp[i] = max(arr[i], dp[i-1] + arr[i]) | | 初始 | dp[0] = arr[0] |

def max_subarray(arr):
    dp = [0] * len(arr)
    dp[0] = arr[0]
    for i in range(1, len(arr)):
        dp[i] = max(arr[i], dp[i-1] + arr[i])
    return max(dp)

print(f"最大子陣列: {max_subarray([-2,1,-3,4,-1,2,1,-5,4])}")  # 6

時間複雜度比較

| 問題 | 沒 DP | 有 DP | 改善效果 | |------|-------|-------|---------| | 費氏數列(n) | O(2ⁿ) | O(n) | 指數→線性 | | 最大子陣列(n) | O(n²) | O(n) | 平方→線性 | | 背包問題(n,W) | O(2ⁿ) | O(nW) | 指數→偽多項式 | | LCS(n,m) | O(2ⁿ⁺ᵐ) | O(nm) | 指數→平方 |

總結

| 面向 | 重點 | |------|------| | 記憶化 | Top-Down 遞迴 + 快取 | | 表格法 | Bottom-Up 迭代陣列 | | 狀態定義 | 最關鍵的步驟 — 決定整個解法走向 | | 遞迴關係 | 連結子問題的核心公式 | | 初始條件 | 沒有 base case 就沒有遞迴的基礎 | | 空間優化 | 常可從 O(n) 降到 O(1) |

DP 的兩個關鍵性質

一個問題能不能用 DP 解，取決於它是否具備兩個性質：

1. 最優子結構（Optimal Substructure）

大問題的最佳解可以由小問題的最佳解推導出來。

✅ Fibonacci：F(5) = F(4) + F(3)
✅ 最短路徑：A→C 的最短路徑經過 B，則 A→B 和 B→C 也分別是最短路徑
❌ 最長路徑（無環路除外）：子路徑不一定是最長

2. 重疊子問題（Overlapping Subproblems）

不同的決策路徑會遇到相同的子問題。

✅ Fibonacci：計算 F(5) 需要 F(4) 和 F(3)，計算 F(4) 也需要 F(3)
❌ 二元搜尋：每次切一半，子問題不重疊（這是 Divide & Conquer）

Top-Down vs Bottom-Up

| 方法 | 寫法 | 優點 | |:----|:----|:----| | Top-Down（記憶化遞迴） | 遞迴 + cache | 直覺、只算需要的狀態 | | Bottom-Up（迭代 DP） | for 迴圈 + 表格 | 無遞迴成本、容易最佳化空間 |

下一章預告：0/1 背包問題

學會 DP 核心觀念後，下一章用最經典的 0/1 背包問題來實戰——狀態怎麼定義、表格怎麼填、一維陣列怎麼優化。