動態規劃：把算過的記下來

想像你在爬樓梯

樓梯有 n 階，你一次可以跨 1 階或 2 階。 問：到第 n 階有幾種爬法？

先用小例子試試看：

n	爬法	種類數
1	(1)	1
2	(1,1) 或 (2)	2
3	(1,1,1)(1,2)(2,1)	3
4	(1,1,1,1)(1,1,2)(1,2,1)(2,1,1)(2,2)	5
5	?	8

看出規律了嗎？1, 2, 3, 5, 8, 13, … 就是費氏數列！

為什麼？ 要到第 n 階，最後一步要嘛從 n-1 跨 1 階上來，要嘛從 n-2 跨 2 階上來。所以 f(n) = f(n-1) + f(n-2)。

用遞迴寫（會慢）

Algorithm climb(n):

if n ≤ 2: return n

return climb(n-1) + climb(n-2)

跟費氏數列一樣，n=50 就跑不完。為什麼？重複計算。

解法 1：記憶化（Top-Down DP）

算過的存起來，下次直接拿。這個技巧叫 Memoization（記憶化）。

memo ← {}

Algorithm climb(n):

if n ≤ 2: return n

if n in memo: return memo[n] // 算過？直接拿

memo[n] ← climb(n-1) + climb(n-2)

return memo[n]

複雜度從 O(2ⁿ) 變 O(n)——指數變線性，這就是 DP 的威力。

解法 2：跑迴圈（Bottom-Up DP）

不用遞迴，從小到大算上去：

Algorithm climb(n):

dp[1] ← 1, dp[2] ← 2

for i ← 3 to n:

dp[i] ← dp[i-1] + dp[i-2]

return dp[n]

同樣 O(n)，但沒有遞迴的堆疊成本，實務上更快。

💡DP 的本質

DP = 遞迴 + 記憶化 或 DP = 從小問題堆積到大問題。兩種寫法答案一樣，看你習慣哪一種。

經典題 2：湊零錢

問：有面額 1、5、10、25 元的硬幣，要湊出 N 元，最少幾枚？

例：N = 30，最少 2 枚（25+5）。N = 11，最少 3 枚（10+1，沒辦法更少）。

思路

要湊出 N 元，最後一枚硬幣一定是 1, 5, 10, 25 其中一個：

用 1：剩下要湊 N-1 → 子問題 f(N-1)
用 5：剩下要湊 N-5 → 子問題 f(N-5)
用 10：剩下要湊 N-10 → 子問題 f(N-10)
用 25：剩下要湊 N-25 → 子問題 f(N-25)

f(N) = 1 + min(f(N-1), f(N-5), f(N-10), f(N-25))

Base case：f(0) = 0（湊 0 元用 0 枚）。

Algorithm coinChange(N):

dp[0] ← 0

for i ← 1 to N:

dp[i] ← ∞

for coin in {1, 5, 10, 25}:

if i ≥ coin:

dp[i] ← min(dp[i], dp[i - coin] + 1)

return dp[N]

複雜度：O(N × 硬幣種類) = O(N)。

怎麼看出一題是 DP？

問自己這三個問題：

能不能切成子問題？ 大問題能不能用「同類型的小問題」描述？
子問題會重複出現嗎？ 如果是，DP 能省下大量計算。
能寫出狀態轉移方程嗎？ 也就是 f(n) = ...f(更小的東西)... 這種式子。

三個都 yes → DP 八成可以解。

📝考試會這樣考

題型一：給狀態轉移方程，要你填表。

例：f(i) = f(i-1) + f(i-2)、f(0)=1, f(1)=1。算 f(6)。

i	0	1	2	3	4	5	6
f(i)	1	1	2	3	5	8	13

題型二：列出湊零錢題的 DP 表。

N=11，硬幣 {1,5,10}，列出 dp[0] 到 dp[11]：

i	0	1	2	3	4	5	6	7	8	9	10	11
dp[i]	0	1	2	3	4	1	2	3	4	5	1	2

題型三：寫出狀態轉移方程。 給題目要你寫出 f(n) = ... 的數學式。這是 DP 題的核心，寫得出方程就成功一半。

題型四：問為什麼某題能用 DP？ 答：因為有「最佳子結構」（大問題的最優解可由子問題的最優解組成）+「重複子問題」（同一個子問題會被算很多次）。

這章記住

DP = 算過的別再算。
兩種寫法：遞迴 + 記憶化（top-down）vs 迴圈填表（bottom-up）。
看到「最佳化問題 + 能切成子問題 + 子問題重複」就想 DP。
寫出狀態轉移方程是核心，方程寫對程式就好寫了。