貪心就是「每一步都選當下最好的，然後祈禱最後結果也是最好的」。有時候靈，有時候不靈。關鍵是你要知道什麼時候靈。
先講結論
貪心能用的時候比 DP 快很多，但它只在問題具有「貪心選擇性質」時才正確。如果你不確定能不能用貪心——那大概不能用，乖乖寫 DP。
| 比較 | 貪心 | DP |
|---|---|---|
| 策略 | 每步選最佳 | 考慮所有可能 |
| 回溯 | 不回頭 | 會比較不同選擇 |
| 速度 | 通常 O(n log n) | 通常 O(n²) 以上 |
| 正確性 | 不一定最佳 | 保證最佳 |
貪心的陷阱
找零 63 元，硬幣 [1, 5, 10, 25]：
- 貪心：25+25+10+1+1+1 = 6 枚 → 正確
找零 6 元，硬幣 [1, 3, 4]：
- 貪心：4+1+1 = 3 枚
- 最佳：3+3 = 2 枚 → 貪心錯了！
同樣是硬幣找零，換一組硬幣就爆了。這就是為什麼你不能「覺得」可以用貪心就用貪心，你要能證明它的正確性。
四個靠譜的貪心問題
1. 活動選擇
選最多不重疊的活動。貪心策略：每次選結束最早的。
活動: [(1,2), (3,4), (0,6), (5,7), (8,9)]
按結束時間排序後選：(1,2) → (3,4) → (5,7) → (8,9)
共 4 個
Arrays.sort(activities, (a, b) -> a.end - b.end);
List<Activity> selected = new ArrayList<>();
int lastEnd = 0;
for (Activity act : activities) {
if (act.start >= lastEnd) {
selected.add(act);
lastEnd = act.end;
}
}為什麼結束最早是對的？因為結束越早，就給後面的活動留越多空間。這不是直覺，這是可以數學證明的。
2. 分數背包
跟 0/1 背包不同，物品可以切割。策略：按價值密度（$/kg）排序，從最值錢的開始拿。
物品: [(10kg, $60), (20kg, $100), (30kg, $120)]
背包 50kg，價值密度: 6, 5, 4
全拿物品0(10kg, $60) + 全拿物品1(20kg, $100) + 物品2的 2/3(20kg, $80)
= $240
注意：0/1 背包（不能切割）就不能用貪心了，要用 DP。
3. 霍夫曼編碼
壓縮的基礎。策略：頻率越高的字元用越短的編碼。
字元頻率: a=45, b=13, c=12, d=16, e=9, f=5
每次合併頻率最小的兩個：
f(5) + e(9) = 14 → c(12) + b(13) = 25 → ...
結果：a 用 1 bit，f 用 4 bits
你用的 zip、gzip、png，背後都有霍夫曼的影子。
4. Kruskal 最小生成樹
連接所有節點的最小權重邊集合。策略：按邊權重排序，每次選最小且不形成環的。
用 Union-Find 判斷是否成環，整體 O(E log E)。
貪心 vs DP 怎麼選
問題是否有貪心選擇性質？
├─ 是 → 貪心（更快）
│ ├─ 活動選擇
│ ├─ 分數背包
│ ├─ 霍夫曼編碼
│ └─ MST
└─ 不確定 / 否 → DP（保證正確）
├─ 0/1 背包
├─ 硬幣找零（某些硬幣組合）
└─ LCS
我的建議：面試時如果你覺得可以用貪心，先用貪心寫，然後跟面試官解釋為什麼貪心是對的。如果你解釋不出來，那就回去寫 DP。「解釋為什麼貪心是對的」這件事本身就能讓面試官印象深刻。
貪心的萬用模板
// 1. 排序
Arrays.sort(items, comparator);
// 2. 逐一貪心選擇
for (Item item : items) {
if (canSelect(item)) {
select(item);
updateState();
}
}幾乎所有貪心問題都符合這個結構：排序 → 遍歷 → 選或不選。差別只在排序的依據和選擇的條件。
貪心演算法就像人生的很多決策：每次選當下看起來最好的，然後希望最後結果不會太差。差別是演算法可以數學證明，人生不行。