DP 不是什麼神秘的東西。你每天都在用：
git diff是 LCS、手機自動校正是 Edit Distance、Webpack code splitting 是背包問題。只是你不知道而已。
先講結論
DP 的本質就一句話：把重複算過的東西記下來，不要再算一次。很多人覺得 DP 難，是因為他們直接跳去寫狀態轉移式。其實 DP 有一套固定的思考流程：暴力遞迴 → 畫樹找重複 → 加 memo → 轉 bottom-up。照這個走，八成的 DP 題你都能解。
你每天都在用 DP
| 工程場景 | 對應 DP 問題 |
|---|---|
git diff | LCS（最長共同子序列） |
| 手機鍵盤自動校正 | Edit Distance（編輯距離） |
| Webpack code splitting | 背包問題 |
| 資料庫 query optimizer | 矩陣鏈乘積 |
| 股票交易策略回測 | 買賣股票問題 |
不是在背題，是這些工具的底層真的就長這樣。
DP 的兩種做法
Top-Down：記憶化遞迴
從大問題往下拆，算過的存起來直接查。適合剛開始理解 DP 的人，因為思路就是遞迴。
int[] memo = new int[n + 1];
int fib(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}Bottom-Up：表格法
從最小的子問題開始往上填表。沒有遞迴 overhead，通常空間效率也更好。
int fib(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}兩種方法的結果一樣。Top-Down 比較好想，Bottom-Up 比較好優化。我個人的習慣是先用 Top-Down 確認思路正確，再轉成 Bottom-Up。
四步思考框架：從暴力到最佳解
Step 1：先寫暴力遞迴
不要想最佳化，用最笨的方法解。這一步最重要。
// 硬幣找零：用最少硬幣組成 amount
function coinChange(coins: number[], amount: number): number {
if (amount === 0) return 0;
if (amount < 0) return Infinity;
let min = Infinity;
for (const coin of coins) {
const result = coinChange(coins, amount - coin);
min = Math.min(min, result + 1);
}
return min;
}Step 2：畫遞迴樹，找重疊子問題
coinChange([1,2,5], 6)
├── coinChange(5)
│ ├── coinChange(4)
│ │ ├── coinChange(3) ← 重複！
│ │ └── ...
│ └── coinChange(3) ← 重複！
├── coinChange(4) ← 重複！
└── coinChange(1)
coinChange(3) 和 coinChange(4) 被算了好幾次。有重疊 → 能用 DP。
Step 3：加 memo
function coinChange(coins: number[], amount: number): number {
const memo = new Map<number, number>();
function dp(remaining: number): number {
if (remaining === 0) return 0;
if (remaining < 0) return Infinity;
if (memo.has(remaining)) return memo.get(remaining)!;
let min = Infinity;
for (const coin of coins) {
min = Math.min(min, dp(remaining - coin) + 1);
}
memo.set(remaining, min);
return min;
}
const result = dp(amount);
return result === Infinity ? -1 : result;
}Step 4：轉成 Bottom-Up
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// coinChange([1, 2, 5], 11) → 3（5+5+1）怎麼判斷是不是 DP 問題？
問自己三個問題：
- 是不是在求「最大/最小/最長/最短」或「有幾種方法」？
- 能不能拆成子問題？
- 子問題會不會被重複計算？
三個都是 → DP。前兩個是但第三個不是 → 可能是分治法。只有第一個是 → 可能是貪心。
空間優化
如果 dp[i] 只依賴 dp[i-1]，可以把整個陣列壓成兩個變數：
int prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
int next = prev + curr;
prev = curr;
curr = next;
}從 O(n) 空間降到 O(1)。面試官會對你刮目相看，但你的程式碼可讀性也會讓同事對你刮目相看。
經典 DP 問題的詳解請看 動態規劃（下）：六個經典問題。
DP 最難的部分不是寫程式，是定義狀態。一旦狀態定對了，轉移式通常就很明顯。定不出來？先寫暴力解，答案就在遞迴的參數裡。