動態規劃
Dynamic Programming
從「重複計算」到「記憶答案」：一套可以套用在七種經典題型上的解題框架。
費氏數列
零錢兌換
最長遞增子序列
0/1 背包
最長共同子序列
編輯距離
矩陣鏈乘法
SECTOOLS.TW
演算法系列
演算法系列
課程地圖
六個章節，一條路線
01
為什麼需要 DP
從費氏數列的重複計算，看見記憶化的價值
02
解題五步框架
狀態、轉移、邊界、順序、答案
03
一維 DP
零錢兌換、最長遞增子序列
04
背包問題
0/1 背包與空間壓縮技巧
05
雙序列 DP
最長共同子序列、編輯距離
06
區間 DP
矩陣鏈乘法與填表順序
帶著 ▶ 標記的頁面可以逐步播放填表過程
01
為什麼需要動態規劃
同一個子問題被算了幾千次，這就是遞迴慢下來的原因。
01 · 為什麼需要動態規劃
起點：費氏數列的樸素遞迴
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
# 定義完全正確，但每次呼叫都
# 把整棵子樹重新算一遍
fib(20) 的函式呼叫次數
21,891
fib(30)
2,692,537
fib(50)
約 407 億
n 每加 1，工作量幾乎翻倍。這是 O(2ⁿ) 的成長速度。
01 · 為什麼需要動態規劃
遞迴樹裡的重複子問題
樸素遞迴 · fib(5) 展開後 15 個節點
f(5)
f(4)f(3)
f(3)f(2)f(2)f(1)
f(2)f(1)f(1)f(0)f(1)f(0)
橘色是重複出現的子問題：f(3) 算了 2 次，f(2) 算了 3 次
加上記憶化 · 只剩 6 個節點
f(0)
f(1)
f(2)
f(3)
f(4)
f(5)
每個子問題只算一次，算完存起來；下次遇到直接查表。
節點數從
2ⁿ → n + 1
動態規劃的全部祕密，就是這一句話。
01 · 為什麼需要動態規劃
能用 DP 的兩個前提
01
最佳子結構
Optimal Substructure
大問題的最佳解，可以由小問題的最佳解直接組合出來。
自我檢查：如果我已經知道所有更小規模的答案，能不能一步算出現在這個答案？
02
重疊子問題
Overlapping Subproblems
同一個子問題會在不同分支被反覆遇到，所以「記下來」才有意義。
自我檢查：把遞迴樹畫兩層，有沒有出現一模一樣的節點？
✕
不符合會怎樣
Counter-examples
沒有重疊子問題 → 用分治法（如合併排序）就好，記表只是浪費空間。
沒有最佳子結構 → 局部最佳拼不出全局最佳，只能搜尋或用其他模型。
01 · 為什麼需要動態規劃
三種寫法：遞迴、記憶化、表格
樸素遞迴
O(2ⁿ)
def fib(n):
if n < 2:
return n
return fib(n-1) \
+ fib(n-2)
定義最直白，但重複計算
記憶化（上而下）
O(n)
from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n-1) \
+ fib(n-2)
保留遞迴思維，一行裝上筆記本
表格法（下而上）
O(n) / O(1)
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
沒有遞迴堆疊，可再壓縮空間
01 · 為什麼需要動態規劃
複雜度差距：從 O(2ⁿ) 到 O(n)
計算 fib(n) 所需的基本步數
21,891
n = 20
2.7 百萬
n = 30
3.3 億
n = 40
407 億
n = 50
50
DP n=50
縱軸為對數示意，僅表達量級差異
n = 50 時的差距
8 億倍
從「跑不完」變成「瞬間完成」
樸素遞迴O(2ⁿ) 時間 · O(n) 空間
記憶化遞迴O(n) 時間 · O(n) 空間
滾動變數表格法O(n) 時間 · O(1) 空間
02
解題的五步框架
寫 DP 不靠靈感。難的永遠只是第一步：定義狀態。
02 · 解題的五步框架
每一題都走同樣五步
1
定義狀態
dp[i] 到底代表什麼？用一句完整的中文寫下來，不能含糊。
2
寫轉移方程
dp[i] 可以由哪些更小的狀態推出來？列出所有「上一步的選擇」。
3
確定邊界
最小的子問題答案是什麼？通常是 0、1 或無限大。
4
決定計算順序
保證用到的狀態都已經算好了：由小到大、由左到右、或按區間長度。
5
取出答案
答案在表格的哪一格？不一定是最後一格，也可能是整張表的最大值。
02 · 解題的五步框架
狀態轉移方程式的讀法
dp[i][j] = min( dp[i-1][j], dp[i][j-1], dp[i-1][j-1] ) + 1
念法：「我現在要的答案，等於所有可能的上一步裡最好的那一個，再加上這一步的代價。」
dp[i][j]
要求的狀態
現在正在填的那一格，由狀態定義決定它的含義。
min( … )
所有上一步的選擇
括號裡每一項對應一個決策；求最小值用 min，求方案數用相加。
+ 1
這一步的代價
走這一步要付的成本或收益：一枚硬幣、一次修改、一件物品的價值。
02 · 解題的五步框架
什麼時候該用動態規劃
題目在問「最大 / 最小 / 有幾種方法」？
↓ 是
每一步的選擇會影響後面的選擇？
↓ 是
畫兩層遞迴樹，有重複節點？
↓ 是
用動態規劃
若「選擇不互相影響」
每一步取當下最好就是全局最好 → 貪心法（Greedy）
若「沒有重複子問題」
子問題彼此獨立 → 分治法（Divide & Conquer）
若「要列出所有可能」
需要具體方案而非數量 → 回溯法（Backtracking）
最常見的誤判
看到「最少」就用貪心。下一章的零錢兌換就是貪心會答錯的例子。
03
一維 DP
零錢兌換與最長遞增子序列：狀態只有一個下標。
03 · 一維 DP
零錢兌換：問題與狀態定義
題目
手上有面額 1、3、4 元的硬幣，數量不限。要湊出 6 元，最少需要幾枚？
貪心法會怎麼做
4 + 1 + 1 → 3 枚
先拿最大面額，剩下再補。看起來合理。
正確答案
3 + 3 → 2 枚
貪心在這裡失效：這一步拿最大，會讓剩下的部分變得更難湊。
① 定義狀態
dp[i] = 湊出金額 i 元所需的最少硬幣數
② 轉移方程
dp[i] = min(dp[i - c] + 1)
對每種硬幣 c：假設最後放下的是 c，剩下 i−c 元的最佳解已經算好了。
③ 邊界
dp[0] = 0，其餘 = ∞
④ 順序
i 由小到大
⑤ 答案
dp[6]
03 · 一維 DP ▶ 逐步演示
零錢兌換：一格一格填出答案
金額 0 → 6 元，硬幣 1 / 3 / 4
{{ coinGrid }}
{{ coinPos }}
這一步的方程式
{{ coinEq }}
說明
{{ coinNote }}
正在計算
參考來源
已完成
03 · 一維 DP
零錢兌換：Python 實作
def coin_change(coins, amount):
INF = float('inf')
dp = [0] + [INF] * amount
for i in range(1, amount + 1):
for c in coins:
if c <= i:
dp[i] = min(dp[i], dp[i - c] + 1)
return -1 if dp[amount] == INF else dp[amount]
# coin_change([1, 3, 4], 6) → 2
兩層迴圈＝五步的第 4 步
外層走金額（由小到大），內層走所有選擇（每種硬幣）。
為什麼用 ∞ 當初值
代表「還湊不出來」。取 min 時它永遠輸，也讓最後能判斷無解。
時間複雜度
O(amount × 硬幣數)
變體練習
把 min 換成加總，就變成「湊出 i 元有幾種組合」；此時迴圈順序會決定是否算重複，值得單獨想清楚。
03 · 一維 DP
最長遞增子序列：狀態定義
輸入陣列
3
1
4
2
8
6
7
橘色為一組最長遞增子序列
1 → 4 → 6 → 7，長度 4
① 定義狀態
dp[i] = 以 i 結尾的最長遞增子序列長度
「以 i 結尾」這四個字是關鍵：它讓子問題之間可以接續。
② 轉移方程
dp[i] = max(dp[j]) + 1
其中 j < i 且 a[j] < a[i]
其中 j < i 且 a[j] < a[i]
③ 邊界
每個 dp[i] 至少是 1（自己一個人也算一組）
⑤ 答案在哪
不是 dp[n−1]，而是整張表的最大值：最長的子序列不一定結束在最後一個元素。
03 · 一維 DP ▶ 逐步演示
最長遞增子序列：逐格推進
上排為陣列值，下排為 dp 值
{{ lisGrid }}
{{ lisPos }}
這一步的方程式
{{ lisEq }}
說明
{{ lisNote }}
兩層迴圈 → O(n²)
另有「貪心 + 二分搜尋」的 O(n log n) 寫法，等這個版本熟了再學。
04
背包問題
「拿或不拿」是最常見的決策原型，狀態從此變成兩維。
04 · 背包問題
0/1 背包：問題與兩維狀態
四件物品，背包限重 5 kg
物品重量價值單位價值
A2 kg$31.50
B3 kg$41.33
C4 kg$51.25
D5 kg$61.20
貪心又失效了
按單位價值先拿 A（2kg），再拿 B（3kg）剛好裝滿得 $7 —— 這次對了；但把容量改成 4 kg，貪心拿 A 之後裝不下 B，只得 $3，最佳解其實是 C 的 $5。
① 定義狀態
dp[i][j] = 只考慮前 i 件物品、容量為 j 時的最大價值
② 轉移方程：兩個選擇
不拿 i：dp[i-1][j]
拿 i：dp[i-1][j-w] + v
dp[i][j] = max(兩者)
拿 i：dp[i-1][j-w] + v
dp[i][j] = max(兩者)
注意兩個選項都來自 i−1 列：物品只能用一次。
③ 邊界
第 0 列與第 0 欄皆為 0
⑤ 答案
dp[4][5]（右下角）
04 · 背包問題 ▶ 逐步演示
0/1 背包：二維表格填法
橫軸為背包容量 0 → 5
{{ knapGrid }}
{{ knapPos }}
這一步的方程式
{{ knapEq }}
說明
{{ knapNote }}
04 · 背包問題
把二維表壓成一維
def knapsack(items, W):
dp = [0] * (W + 1)
for w, v in items:
# 容量必須「倒著」走
for j in range(W, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
return dp[W]
# 空間 O(nW) → O(W)
為什麼只需要一列
dp[i][j] 只用到 i−1 列。既然更早的列再也用不到，就讓新值直接覆蓋舊值。
為什麼容量要倒著走
倒著走時 dp[j−w] 還是上一列的值（沒放過這件物品）。正著走會讀到本列剛更新的值，等於同一件物品拿了兩次。
記住這組對照
容量倒著走 → 0/1 背包（每件一次）
容量正著走 → 完全背包（每件可無限次）
容量正著走 → 完全背包（每件可無限次）
05
雙序列 DP
兩個字串各出一個下標，格子的意義是「兩邊各看到哪裡」。
05 · 雙序列 DP
最長共同子序列：狀態與轉移
兩個字串
A
B
C
B
B
D
C
B
共同子序列 B C B，長度 3。子序列不必連續，但順序不能改。
① 定義狀態
dp[i][j] = s1 的前 i 個字元與 s2 的前 j 個字元的最長共同子序列長度
② 轉移：只有兩種情況
字元相同 s1[i] == s2[j]
dp[i][j] = dp[i-1][j-1] + 1
這個字元一定值得配對，兩邊同時往前退一格。
字元不同
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
放棄其中一邊的最後一個字元，取比較好的那個選擇。
為什麼多一列多一欄
第 0 列 / 第 0 欄代表「空字串」，長度為 0。多這一圈邊界，程式裡就不必寫一堆 if 判斷下標。
05 · 雙序列 DP ▶ 逐步演示
最長共同子序列：填表與回溯
列為 ABCB，欄為 BDCB
{{ lcsGrid }}
{{ lcsPos }}
這一步的方程式
{{ lcsEq }}
說明
{{ lcsNote }}
要還原答案字串
從右下角往回走：值來自左上斜角就記下該字元，否則往數值較大的方向移動。
05 · 雙序列 DP
編輯距離：三個操作、三個來源
刪除
dp[i-1][j] + 1
來自上方：把 s1 的第 i 個字元丟掉。
插入
dp[i][j-1] + 1
來自左方：補上 s2 的第 j 個字元。
替換
dp[i-1][j-1] + 1
來自左上斜角：把字元改成一樣。若本來就相同則 +0。
def edit_distance(a, b):
# dp 為 (m+1)×(n+1) 的表；dp[i][0] = i、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], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
邊界的意義
dp[i][0] = i：把長度 i 的字串變成空字串，要刪 i 次。第 0 欄同理。
實務上在哪裡用
拼字建議、diff 工具、DNA 序列比對、模糊搜尋的相似度排序。
複雜度
O(m × n) 時間
O(m × n) → O(n) 空間
O(m × n) → O(n) 空間
05 · 雙序列 DP ▶ 逐步演示
編輯距離：horse → ros
列為 horse，欄為 ros
{{ editGrid }}
{{ editPos }}
這一步的方程式
{{ editEq }}
說明
{{ editNote }}
最終答案 3
horse → rorse（替換 h→r）→ rose（刪除 r）→ ros（刪除 e）
06
區間 DP
矩陣鏈乘法：狀態是一段區間，還要多一個切點。
06 · 區間 DP
矩陣鏈乘法：順序決定代價
A 10×30
×
B 30×5
×
C 5×60
結果都是 10×60，但乘法次數差很多
(A × B) × C
10×30×5 = 1,500
10×5×60 = 3,000
10×5×60 = 3,000
4,500
次乘法
A × (B × C)
30×5×60 = 9,000
10×30×60 = 18,000
10×30×60 = 18,000
27,000
次乘法 · 整整 6 倍
① 定義狀態
dp[i][j] = 把第 i 到第 j 個矩陣乘完的最少乘法次數
② 轉移：枚舉切點 k
dp[i][j] = min over k of
dp[i][k] + dp[k+1][j]
+ p[i-1]·p[k]·p[j]
dp[i][k] + dp[k+1][j]
+ p[i-1]·p[k]·p[j]
06 · 區間 DP
填表順序：按區間長度由短到長
只需填上三角，顏色代表區間長度
i \ j1234
10ℓ2ℓ3ℓ4
20ℓ2ℓ3
30ℓ2
40
對角線是長度 1 的區間（不用乘），答案在右上角 dp[1][4]。
for L in range(2, n + 1): # 區間長度
for i in range(1, n - L + 2):
j = i + L - 1
dp[i][j] = INF
for k in range(i, j): # 切點
cost = (dp[i][k] + dp[k+1][j]
+ p[i-1] * p[k] * p[j])
dp[i][j] = min(dp[i][j], cost)
為什麼要按長度填
長區間會被切成兩段更短的區間。要保證用到的值都算好了，就得先把短的填完。
三層迴圈
O(n³) 時間 · O(n²) 空間
總結
七題一覽：狀態與複雜度
題目
狀態定義
時間
空間
費氏數列
dp[i] = 第 i 項的值
O(n)
O(1)
零錢兌換
dp[i] = 湊出 i 元的最少硬幣數
O(nW)
O(W)
最長遞增子序列
dp[i] = 以 i 結尾的最長長度
O(n²)
O(n)
0/1 背包
dp[i][j] = 前 i 件、容量 j 的最大價值
O(nW)
O(W)
最長共同子序列
dp[i][j] = 兩邊前 i、前 j 的最長長度
O(mn)
O(n)
編輯距離
dp[i][j] = 前 i 變成前 j 的最少操作數
O(mn)
O(n)
矩陣鏈乘法
dp[i][j] = 乘完第 i 到 j 的最少次數
O(n³)
O(n²)
總結
六個最常見的錯誤
01
狀態定義含糊
寫不出一句完整中文，就一定寫不出轉移方程。先把定義寫成句子。
02
邊界少一格
n+1 大小的表格、第 0 列代表空狀態，能省掉大量下標判斷。
03
迴圈方向寫反
壓縮成一維後方向就是語意：倒著是 0/1，正著是完全背包。
04
答案取錯格子
LIS 的答案是整張表的最大值，不是最後一格。先問「答案在哪」。
05
初值用 0 代替無限大
求最小值時 0 會贏過一切，讓表格全被污染。該用 ∞ 就用 ∞。
06
直接背程式碼
DP 的程式碼都長得很像，背了也遷移不了。要背的是五步流程。
總結
接下來這樣練
STEP 1
建立直覺
爬樓梯
打家劫舍
最大子陣列和
打家劫舍
最大子陣列和
全部一維，先練「定義狀態」這一步
STEP 2
兩維狀態
分割等和子集
目標和
不同路徑 II
目標和
不同路徑 II
練習把「選或不選」翻成兩維表格
STEP 3
變形與優化
買賣股票的最佳時機 III
迴文分割 II
戳氣球
迴文分割 II
戳氣球
狀態機 DP 與區間 DP，難度明顯跳階
HABIT
每題都做這件事
先用中文寫下狀態定義，再動手寫程式。寫不出來就不要開始打字。
先寫記憶化版本，再改寫成表格法
SECTOOLS.TW · 演算法系列
帶走這三句話
01
DP 就是把算過的答案記下來
重疊子問題是它有效的唯一理由；沒有重複，就不需要表格。
02
難的是定義狀態，不是寫程式
狀態定義寫得夠精確，轉移方程幾乎會自己浮現。
03
七種題型，一套五步框架
狀態、轉移、邊界、順序、答案。每一題都照這個順序問自己一次。
問題與討論
EMPOWERING YOUR CYBERSECURITY, ONE TOOL AT A TIME.