如果你還沒看過 上篇的思考框架，建議先看。這篇直接拆解六個經典題目。
先講結論
DP 經典題其實就那幾個模式：一維線性、二維矩陣、背包、區間。搞懂這六題，面試和實務的 DP 問題你大概能應付七八成。
1. 費波那契 & 爬樓梯
這兩題的狀態轉移式一模一樣：dp[i] = dp[i-1] + dp[i-2]。
爬樓梯問題：每次可以爬 1 或 2 階，到第 n 階有幾種方法？
到第 1 階：1 種 (1)
到第 2 階：2 種 (1+1, 2)
到第 3 階：3 種 (1+1+1, 1+2, 2+1)
到第 4 階：5 種
為什麼跟費波那契一樣？因為到第 n 階，你不是從 n-1 跨一步來，就是從 n-2 跨兩步來。方法數就是兩者加總。
面試小技巧：如果面試官問你爬樓梯，不要只寫出來，要能解釋為什麼它是費波那契。
2. 最長共同子序列 LCS
ABCDE 和 ACE → LCS = ACE，長度 3。
如果 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]) // 跳過其中一個
填表長這樣（s1 = “ACE”, s2 = “ABCDE”）：
"" A B C D E
"" 0 0 0 0 0 0
A 0 1 1 1 1 1
C 0 1 1 2 2 2
E 0 1 1 2 2 3
工程場景：git diff 就是 LCS
git diff 先找出兩個版本的共同行（LCS），剩下的就是 +（新增）和 -（刪除）。
function simpleDiff(oldLines: string[], newLines: string[]): string[] {
const m = oldLines.length, n = newLines.length;
const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (oldLines[i - 1] === newLines[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 回溯產生 diff 輸出
const result: string[] = [];
let i = m, j = n;
while (i > 0 || j > 0) {
if (i > 0 && j > 0 && oldLines[i - 1] === newLines[j - 1]) {
result.unshift(` ${oldLines[i - 1]}`);
i--; j--;
} else if (j > 0 && (i === 0 || dp[i][j - 1] >= dp[i - 1][j])) {
result.unshift(`+ ${newLines[j - 1]}`);
j--;
} else {
result.unshift(`- ${oldLines[i - 1]}`);
i--;
}
}
return result;
}下次你打 git diff 的時候，想一下背後那張 O(m×n) 的表格。
3. 0/1 背包問題
物品有重量和價值，背包容量有限，求最大價值。每個物品只能選一次。
物品: [(重量=2, 價值=3), (重量=3, 價值=4), (重量=4, 價值=5)]
背包容量: 5
最佳選擇: 物品0 + 物品1 = 價值 7
狀態轉移：對每個物品，你只有兩個選擇——拿或不拿。
dp[i][w] = max(
dp[i-1][w], // 不拿
dp[i-1][w-weight[i]] + value[i] // 拿
)
背包問題在工程中的化身？Webpack 的 code splitting 要決定哪些 module 打包在一起、每個 chunk 不超過多大——本質上就是背包。
4. 硬幣找零
硬幣 [1, 2, 5]，金額 11 → 最少 3 枚 (5+5+1)。
dp[0] = 0
dp[1] = dp[0] + 1 = 1 (用 1)
dp[2] = dp[0] + 1 = 1 (用 2)
dp[3] = dp[1] + 1 = 2 (1+2)
dp[5] = dp[0] + 1 = 1 (用 5)
dp[11] = dp[6] + 1 = 3 (5+5+1)
這題的完整思考過程（暴力→memo→bottom-up）在上篇已經走過一遍，這裡就不重複了。
5. 最長遞增子序列 LIS
[10, 9, 2, 5, 3, 7, 101] → LIS = [2, 3, 7, 101]，長度 4。
對於每個 i:
dp[i] = max(dp[j] + 1) 其中 j < i 且 nums[j] < nums[i]
O(n²) 的解法很直觀，但面試如果問你能不能更快——可以用二分搜尋 + 貪心做到 O(n log n)。維護一個 tails 陣列，每次用 lower bound 找該插入的位置。這個優化我第一次看的時候覺得是黑魔法。
時間複雜度對照
| 問題 | 暴力 | DP |
|---|---|---|
| 費波那契 | O(2^n) | O(n) |
| LCS | O(2^(m+n)) | O(m×n) |
| 背包 | O(2^n) | O(n×W) |
| 硬幣找零 | 指數級 | O(n×amount) |
| LIS | O(2^n) | O(n²) / O(n log n) |
從指數降到多項式，這就是 DP 的威力。
什麼時候不需要 DP
DP 就像存錢：你今天多花一點時間記住結果，明天就不用重新計算。人生的 DP 表格如果也能這樣查就好了。