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

從費氏數列開始

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

# 記憶化版（O(n) — 超快）
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)

print(fib_memo(50))  # 瞬間輸出

Vibe Prompt：讓 AI 幫你推 DP

🔥 詠唱：「幫我把這個遞迴改為 DP 表格填表法，輸出完整的 dp 陣列。」

def fib_dp(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[n]

DP 解題三步驟

1. 定義狀態：dp[i] 代表什麼？
2. 遞迴關係：dp[i] 跟 dp[i-1] 有什麼關係？
3. 初始條件：base case 是什麼？