動態規劃（Dynamic Programming）
動態規劃（Dynamic Programming，DP） 是把一個大問題拆成一系列小問題，並且把每個小問題的答案記下來、只算一次的解題法。它常被形容成「有記憶的遞迴」或「有策略的窮舉」。面試裡它幾乎是必考大題，卡住的人多半不是不會寫迴圈，而是想不出狀態怎麼定義。這篇就把重點放在「怎麼想出來」。
什麼時候能用 DP：兩個前提
一個問題能用 DP 解，通常要同時滿足兩個條件：
1. 重疊子問題（Overlapping Subproblems）
同一個子問題會被重複計算很多次。最經典的例子是費氏數列：算 fib(5) 要算 fib(4) 和 fib(3)，算 fib(4) 又要算 fib(3)⋯⋯fib(3) 被算了不只一次。純遞迴會指數爆炸，DP 把算過的存起來，就降回線性。
如果子問題彼此都不重複（例如純二分搜尋、歸併排序），那是分治（Divide and Conquer），不是 DP——分治沒有「重複計算」可以省，記憶化也就沒有意義。
2. 最優子結構（Optimal Substructure）
大問題的最優解，可以由子問題的最優解組合出來。例如「從第 0 格走到第 n 格的最少花費」，等於「走到前一格的最少花費」再加上最後一步——子問題最優，組出來的就是整體最優。
跟貪心的差別：貪心（Greedy）也倚賴最優子結構，但它每一步只憑當下局部最好的選擇就往下走，不回頭。DP 則是把所有可能的選擇都考慮過再取最好。貪心對的時候比 DP 快，但很多問題貪心會得到錯的答案（例如 coin change 用貪心在某些幣值組合會失敗），這時就得用 DP 全面比較。
一句話記憶：能拆、子問題會重複、而且最優能拼出最優，就是 DP 的訊號。
解題框架：四個步驟
面試時把 DP 拆成四步，任何 DP 題都套得上：
- 定義狀態：
dp[i]（或dp[i][j]）代表什麼？這是最難、也最關鍵的一步。 - 寫轉移方程：
dp[i]怎麼由更小的狀態算出來？ - 邊界條件：最小的狀態（base case）的值是多少？
- 計算順序：先算哪個、後算哪個，保證用到的子狀態都已經算好。
怎麼「想出」狀態（面試最卡的地方）
狀態定義沒有魔法，但有可操作的套路：
- 狀態通常就是「輸入的一個前綴 / 子區間 + 一個限制」。一維陣列題，
dp[i]常是「考慮到第i個元素為止的答案」；兩個字串的題，dp[i][j]常是「第一個字串前i個字、第二個字串前j個字」的答案；背包題多一個維度放「剩餘容量」。 - 從「最後一步」倒推：問「要得到第
i個位置的答案，最後一個動作可能是什麼？」把最後一步的所有可能列出來，每個可能都對應一個更小的子問題——轉移方程就浮現了。這是推導 DP 最實用的思考方式。 - 先寫暴力遞迴，再看參數：如果不確定狀態，先寫一個會 TLE 的遞迴解，那個遞迴函式的參數幾乎就是你的狀態，回傳值就是
dp的值。下面每一題都會示範這個推導。
兩種實作：Top-down vs Bottom-up
同一個轉移方程有兩種寫法：
記憶化搜尋（Top-down / Memoization）：直接照遞迴定義寫，用一個 cache（Python 可用 @lru_cache）記住算過的結果。好處是只算會用到的狀態、程式碼貼近你的思路；壞處是有遞迴呼叫的開銷，深度太大可能爆 stack。
表格法（Bottom-up / Tabulation）：用迴圈從最小狀態往大的填一張表。好處是沒有遞迴開銷、順序明確、方便再做空間優化；壞處是要自己想清楚計算順序。
面試建議：不確定時先用 top-down 把邏輯寫對（因為它幾乎就是暴力遞迴加一行 cache），再視需要改成 bottom-up 或優化空間。
滾動陣列（省空間）
很多 DP 的 dp[i] 只依賴 dp[i-1]（或前幾項），那就不需要保留整張表。把二維壓成一維、或只留兩個變數，空間就從 O(n) 降到 O(1)、或從 O(n×m) 降到 O(m)。這叫滾動陣列（rolling array），是面試官很愛追問的優化點。
經典題型示範
1. 爬樓梯（LeetCode 70）
每次爬 1 或 2 階，爬到第 n 階有幾種走法？
推導：問「到第 n 階，最後一步是什麼？」只有兩種可能——從 n-1 階跨 1 階、或從 n-2 階跨 2 階。所以走法數 = 到 n-1 的走法 + 到 n-2 的走法。
- 狀態：
dp[i]= 爬到第i階的方法數 - 轉移：
dp[i] = dp[i-1] + dp[i-2]（就是費氏數列） - 邊界：
dp[0] = 1、dp[1] = 1
def climb_stairs(n):
prev, cur = 1, 1 # dp[0], dp[1]
for _ in range(2, n + 1):
prev, cur = cur, prev + cur # 滾動陣列，O(1) 空間
return cur
2. 0/1 背包（0/1 Knapsack）
有 n 個物品，各有重量 w[i] 和價值 v[i]，背包容量 W，每個物品最多拿一次，求能裝的最大價值。這是背包家族的原型，很多題目換皮就是它。
推導：對第 i 個物品，最後一步的選擇只有兩種——拿或不拿。不拿，價值 = 用前 i-1 個物品裝容量 c 的最優；拿（前提是裝得下），價值 = v[i] 加上「前 i-1 個物品裝容量 c - w[i]」的最優。兩者取大。
- 狀態：
dp[i][c]= 只考慮前i個物品、容量為c時的最大價值 - 轉移：
dp[i][c] = max(dp[i-1][c], dp[i-1][c - w[i]] + v[i])
def knapsack(weights, values, W):
n = len(weights)
dp = [0] * (W + 1) # 滾動：只留一列
for i in range(n):
# 容量由大到小，確保每個物品只被拿一次
for c in range(W, weights[i] - 1, -1):
dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
return dp[W]
這裡容量迴圈由大到小是 0/1 背包的關鍵細節：這樣更新 dp[c] 時用到的 dp[c - w[i]] 還是「上一輪（前 i-1 個物品）」的值，保證每件物品只拿一次。若改成由小到大，就變成可重複拿的完全背包——面試官很愛考這個區別。
3. 最長遞增子序列 LIS（LeetCode 300）
求陣列中最長的嚴格遞增子序列長度（子序列可不連續）。
推導：問「以第 i 個元素結尾的最長遞增子序列有多長？」它可以接在任何一個 j < i 且 nums[j] < nums[i] 的子序列後面。注意狀態定義成「以 i 結尾」而不是「前 i 個」，是因為要接續就必須知道結尾是誰——這是 LIS 的思考關鍵。
- 狀態：
dp[i]= 以nums[i]結尾的 LIS 長度 - 轉移：
dp[i] = max(dp[j] + 1)，對所有j < i且nums[j] < nums[i] - 邊界：每個
dp[i]至少是 1（自己一個）
def length_of_lis(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp) # 答案是所有結尾裡最長的，不是 dp[-1]
這是 O(n²) 版本。進階可用「二分搜尋 + patience sorting」做到 O(n log n)，維護一個 tails 陣列用 bisect 更新——面試若要求優化，這是標準追問。
4. 編輯距離（LeetCode 72）
把字串 a 變成 b，每次可插入、刪除、替換一個字元，求最少操作次數。這是「兩個字串」型 DP 的代表。
推導：看兩字串的最後一個字元 a[i-1]、b[j-1]。若相同，不用動，問題縮到 dp[i-1][j-1]。若不同，最後一步有三種可能：替換（dp[i-1][j-1]+1）、刪除 a 的字元（dp[i-1][j]+1）、插入（dp[i][j-1]+1），取最小。
- 狀態：
dp[i][j]= 把a的前i個字變成b的前j個字的最少操作 - 邊界：
dp[0][j] = j（全靠插入）、dp[i][0] = i（全靠刪除）
def min_distance(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # 替換
dp[i - 1][j], # 刪除
dp[i][j - 1]) # 插入
return dp[m][n]
同一套「比較最後一個字元」的框架也解 LCS（最長公共子序列）、字串比對等一整類題。
5. Coin Change（LeetCode 322）
給定幣值 coins 和目標金額 amount，每種幣可用無限次，求湊出 amount 的最少硬幣數，湊不出回 -1。
為什麼不能貪心：直覺想「每次拿最大的幣」，但 coins = [1, 3, 4]、amount = 6 時，貪心拿 4+1+1=3 枚，最優其實是 3+3=2 枚。局部最好不等於全局最好，所以要 DP 全面比較。
推導：問「湊出 amount 的最後一枚硬幣是哪種？」若最後一枚是面額 c，那前面就要湊出 amount - c。枚舉所有幣值取最小。
- 狀態：
dp[x]= 湊出金額x的最少硬幣數 - 轉移：
dp[x] = min(dp[x - c] + 1)，對每個c in coins且x >= c - 邊界：
dp[0] = 0；其餘初始化成無限大代表「湊不出」
def coin_change(coins, amount):
INF = float('inf')
dp = [0] + [INF] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount] if dp[amount] != INF else -1
附帶：分割等和子集（LeetCode 416）
「能不能把陣列分成兩個和相等的子集」——先判總和是否為偶數，若是則問題等價於「能否選出一個子集湊到 sum/2」，這正是0/1 背包的布林版（把價值換成「能否裝滿」）。認出它是背包的變形，就能直接套第 2 題的框架。
面試角度：從暴力遞迴推導到 DP
面試時最穩的流程不是硬想 dp 陣列，而是：
- 先寫暴力遞迴：把問題用遞迴定義出來（通常是「窮舉每一步的選擇」）。這一步展現你理解問題結構。
- 指出重疊子問題：畫出遞迴樹，指給面試官看哪些子問題被重複算——這就是能上 DP 的理由。
- 加記憶化：套一個 cache（
@lru_cache或 dict），暴力遞迴瞬間變成 top-down DP。複雜度從指數降到「狀態數 × 每個狀態的轉移成本」。 - （可選）改 bottom-up 並優化空間：把遞迴改成迴圈填表，再用滾動陣列壓空間。若面試官追問空間優化，這步就是答案。
用 climb stairs 走一遍這個流程：
from functools import lru_cache
def climb_stairs(n):
@lru_cache(None) # 這一行就把暴力遞迴變成 top-down DP
def dfs(i):
if i <= 1:
return 1
return dfs(i - 1) + dfs(i - 2)
return dfs(n)
沒有 @lru_cache 這行，dfs 是 O(2ⁿ) 的暴力遞迴；加上它，每個 i 只算一次，變成 O(n)。這一行的差別，就是 DP 的全部精神——把重複計算換成查表。面試時能清楚講出「這裡有重疊子問題，所以我加記憶化」，比直接默寫一個 dp 陣列更能拿分。
複雜度怎麼估
DP 的時間複雜度有個好記的公式：
總時間 ≈ 狀態數量 × 每個狀態的轉移成本
- 爬樓梯：n 個狀態 × O(1) 轉移 = O(n)
- 背包：n×W 個狀態 × O(1) = O(n·W)
- LIS（樸素版）：n 個狀態 × O(n) 轉移 = O(n²)
- 編輯距離：m×n 個狀態 × O(1) = O(m·n)
空間則看你需要保留多少層狀態——只依賴前一層就能用滾動陣列壓到一維。
一個實用的辨識訊號
題目出現「求最大/最小值」「求方法總數」「能不能達成某目標」，而且答案取決於一連串選擇、每個選擇又會影響後面的選擇時，先想想能不能 DP。若同時發現「暴力窮舉會重複算同樣的子問題」，那基本上就是它了。
LeetCode 對照
| 題號 | 題目 | 型別 |
|---|---|---|
| 70 | Climbing Stairs | 一維入門 / 費氏 |
| 322 | Coin Change | 完全背包 / 湊數 |
| 300 | Longest Increasing Subsequence | 以 i 結尾的一維 DP |
| 72 | Edit Distance | 雙字串二維 DP |
| 416 | Partition Equal Subset Sum | 0/1 背包布林版 |