貪心演算法 — Greedy 策略、正確性證明與經典問題 | 資料結構與演算法
2026/07/05
貪心演算法（Greedy Algorithm） 是一種每個決策步驟都選取當前最優選項的策略——不回溯、不猶豫，直接拿走「眼前最好的」。它的魅力在於極度簡潔與高效；它的挑戰在於，你必須嚴格證明「局部最優」真的能累積成「全域最優」，否則貪心只是貪心，不是正確。
前言
想像超市收銀台找零：你要找 41 元，收銀員不會去思考所有組合，而是直接抓一枚 25 分、一枚 10 分、一枚 5 分、一枚 1 分——每次都選當前能用的最大面額，最終以最少枚數湊齊零錢。這就是貪心策略的日常縮影。
然而，貪心並非萬能。換一套面額（例如 [1, 3, 4]）找 6 元，貪心會選 4+1+1 共 3 枚，但最優解是 3+3 共 2 枚。貪心對嗎？取決於問題結構。
讀完本文，你將能夠：
- 理解貪心選擇性質（Greedy Choice Property）與最優子結構（Optimal Substructure）
- 掌握交換論證法（Exchange Argument）驗證貪心正確性
- 實作活動選擇、Huffman 編碼、跳躍遊戲、加油站等經典題型
- 判斷面試題應用貪心還是動態規劃
核心概念
貪心選擇性質（Greedy Choice Property）
貪心演算法成立的第一個充分條件：全域最優解可以透過一系列局部最優選擇達成。換言之，在第一步做出貪心選擇後，剩餘子問題仍然能導向全域最優，而不需要回頭修改已做的選擇。
這個性質並非所有問題都擁有。動態規劃（Dynamic Programming，DP）也要求最優子結構，但 DP 同時考慮所有子問題的可能組合；貪心則更激進——它假設只需要解決「做完當前選擇後」的那一個子問題。
最優子結構（Optimal Substructure）
貪心演算法成立的第二個條件：問題的最優解包含其子問題的最優解。這與 DP 共享，但貪心只需要解一個子問題（做完當前貪心選擇後的子問題），而 DP 需要解所有子問題。
交換論證法（Exchange Argument）
這是證明貪心正確性最常用的工具，步驟如下：
- 假設存在一個最優解 OPT，它在某個步驟沒有採用貪心選擇
- 執行交換：將 OPT 中那個「非貪心的選擇」替換為「貪心選擇」
- 驗證不損失最優性：證明替換後的方案成本不差於 OPT
若能完成步驟 3，則貪心策略可以逐步將任意最優解「轉化」為使用貪心選擇的方案，從而證明貪心解也是最優解。
活動選擇的交換論證示範：
給定活動集合，若最優解的第一個選擇不是「結束時間最早的活動 A1」，設它選了 A2（結束時間較晚）。由於 A1 結束時間 ≤ A2 結束時間，用 A1 替換 A2 後，後續可用時間只會等於或多於原方案，因此替換後的選法不差於 OPT。交換論證成立，選「最早結束」是正確的貪心策略。
活動選擇問題時間軸
活動選擇問題（Activity Selection Problem）：
給定 n 個活動，每個活動有開始時間 s[i] 和結束時間 f[i]，
選取最多不重疊活動。
各活動時間軸（按結束時間排序）：
時間： 0 1 2 3 4 5 6 7 8 9 10 11
|---|---|---|---|---|---|---|---|---|---|---|---|
A1: [====] f=2 ✓ 選（最早結束）
A2: [========] f=4
A3: [============] f=5
A4: [========] f=6
A5: [====] f=7 ✓ 選（s≥2，且最早結束）
A6: [================] f=9
A7: [========] f=11 ✓ 選（s≥7，且最早結束）
貪心策略：
Step 1：選 A1（結束時間最早，f=2），下次開始時間 ≥ 2
Step 2：略過 A2（s=1 < 2，重疊），略過 A3（s=0 < 2，重疊）
選 A5（s=5 ≥ 2，f=7），下次開始時間 ≥ 7
Step 3：略過 A6（s=1 < 7，重疊）
選 A7（s=7 ≥ 7，f=11）
結果：選取 {A1, A5, A7}，共 3 個活動（最優解）
JS/TS 實作
1. 活動選擇（Interval Scheduling）
按結束時間升序排序後，貪心選擇每個不重疊的最早結束活動。
function activitySelection(intervals: [number, number][]): [number, number][] {
// 按結束時間升序排列（貪心關鍵：必須按結束時間，非開始時間）
intervals.sort((a, b) => a[1] - b[1]);
const result: [number, number][] = [];
let lastEnd = -Infinity;
for (const [start, end] of intervals) {
// 只有當前活動不與上一個選中的活動重疊時才選取
if (start >= lastEnd) {
result.push([start, end]);
lastEnd = end;
}
}
return result;
}
// 測試
const activities: [number, number][] = [[0,2],[1,4],[0,5],[5,7],[1,9],[7,11]];
console.log(activitySelection(activities));
// 輸出：[[0,2],[5,7],[7,11]]
2. 分發餅乾（Assign Cookies，LC 455）
每個孩子有一個「滿足度門檻」g[i]，每塊餅乾有大小 s[j]，一塊餅乾只能給一個孩子，求最多能滿足幾個孩子。
貪心策略：排序後，用最小能滿足當前孩子的餅乾配對，留下較大的餅乾給更難滿足的孩子。
function findContentChildren(g: number[], s: number[]): number {
// 孩子的胃口和餅乾大小都升序排序
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let child = 0; // 當前嘗試滿足的孩子指標
let cookie = 0; // 當前嘗試分配的餅乾指標
while (child < g.length && cookie < s.length) {
// 若當前餅乾能滿足當前孩子，配對成功，移到下一個孩子
if (s[cookie] >= g[child]) {
child++;
}
// 不管配對是否成功，餅乾都消耗掉（或移向下一塊）
cookie++;
}
return child; // 已滿足的孩子數量
}
// 測試
console.log(findContentChildren([1, 2, 3], [1, 1])); // 輸出：1
console.log(findContentChildren([1, 2], [1, 2, 3])); // 輸出：2
3. 跳躍遊戲（Jump Game，LC 55 & 45）
LC 55 — 判斷能否到達終點：
維護當前能到達的最遠位置 maxReach，若任何時刻 i > maxReach 則無法繼續。
function canJump(nums: number[]): boolean {
let maxReach = 0; // 從起點出發，目前能到達的最遠索引
for (let i = 0; i < nums.length; i++) {
// 若當前位置已超過最遠可達位置，表示無法到達此處
if (i > maxReach) return false;
// 更新最遠可達位置
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}
// 測試
console.log(canJump([2, 3, 1, 1, 4])); // 輸出：true
console.log(canJump([3, 2, 1, 0, 4])); // 輸出：false
LC 45 — 最少跳幾次才能到達終點：
貪心直覺：將每一跳視為 BFS 的一層（Layer），每層掃描能到達的最遠位置作為下一層邊界，層數即為跳躍次數。
function jump(nums: number[]): number {
// 貪心直覺：BFS 層級遍歷
// 當前層（currentEnd 以內）能到達的最遠位置，就是下一層的邊界
//
// 例：[2, 3, 1, 1, 4]
// Layer 0（index 0）：nums[0]=2，最遠到 index 2
// Layer 1（index 1-2）：nums[1]=3 → index 4；nums[2]=1 → index 3
// 整層最遠：index 4（終點），第 2 跳到達
// 總跳數：2
const n = nums.length;
let jumps = 0;
let currentEnd = 0; // 當前跳躍層的最遠邊界
let farthest = 0; // 下一跳所能到達的最遠位置
for (let i = 0; i < n - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
// 到達當前層的邊界，必須再跳一次
if (i === currentEnd) {
jumps++;
currentEnd = farthest;
if (currentEnd >= n - 1) break; // 已能到達終點，提早結束
}
}
return jumps;
// 時間：O(n)，空間：O(1)
}
// 測試
console.log(jump([2, 3, 1, 1, 4])); // 輸出：2
console.log(jump([2, 3, 0, 1, 4])); // 輸出：2
4. 加油站（Gas Station，LC 134）
沿著環形公路行駛，每站有油量 gas[i]，到下一站需消耗 cost[i]，找出能完成環繞的起始站（保證答案唯一）。
function canCompleteCircuit(gas: number[], cost: number[]): number {
// 貪心洞察：
// 1. 若 sum(gas) >= sum(cost)，則一定存在解
// 2. 若從 startStation 出發，到達某站 i 時油量為負，
// 則 [startStation, i] 中任何站作為起點都不可行
// → 直接跳到 i+1 作為新候選起點
//
// 為什麼中間的站不行？
// 設 startStation 到 j（中間某站）油量 T ≥ 0
// 從 j 出發到 i 的累計油量 = (startStation 到 i 的累計) - T < 0 - T < 0
// 因此從 j 出發也會在 i 處油量為負，不可行。
const n = gas.length;
let totalGas = 0; // 全程總淨油量（若 < 0 則無解）
let currentGas = 0; // 從候選起點出發的累計油量
let startStation = 0;
for (let i = 0; i < n; i++) {
const net = gas[i] - cost[i]; // 本站淨油量
totalGas += net;
currentGas += net;
if (currentGas < 0) {
startStation = i + 1; // 候選起點移至 i+1
currentGas = 0;
}
}
return totalGas >= 0 ? startStation : -1;
// 時間：O(n)，空間：O(1)
}
// 測試
console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // 輸出：3
console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3])); // 輸出：-1
5. Huffman 編碼（Huffman Encoding）
Huffman 編碼是貪心在資訊壓縮領域的經典應用：高頻字符獲得短編碼，低頻字符獲得長編碼，總編碼長度最短。
貪心策略：每次取頻率最小的兩個節點合併，使用最小堆（Min-Heap）實現。
class MinHeap<T> {
private heap: T[] = [];
constructor(private compare: (a: T, b: T) => number) {}
push(val: T): void {
this.heap.push(val);
this.siftUp(this.heap.length - 1);
}
pop(): T {
const top = this.heap[0];
const last = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = last;
this.siftDown(0);
}
return top;
}
get size(): number { return this.heap.length; }
private siftUp(i: number): void {
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.compare(this.heap[i], this.heap[parent]) < 0) {
[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
i = parent;
} else break;
}
}
private siftDown(i: number): void {
const n = this.heap.length;
while (true) {
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < n && this.compare(this.heap[l], this.heap[smallest]) < 0) smallest = l;
if (r < n && this.compare(this.heap[r], this.heap[smallest]) < 0) smallest = r;
if (smallest === i) break;
[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
i = smallest;
}
}
}
interface HuffmanNode {
char: string | null;
freq: number;
left: HuffmanNode | null;
right: HuffmanNode | null;
}
function buildHuffmanTree(freqMap: Map<string, number>): HuffmanNode {
const pq = new MinHeap<HuffmanNode>((a, b) => a.freq - b.freq);
// 每個字元建立葉節點加入最小堆
for (const [char, freq] of freqMap) {
pq.push({ char, freq, left: null, right: null });
}
// 持續取兩個最小頻率節點合併，直到只剩根節點
while (pq.size > 1) {
const left = pq.pop();
const right = pq.pop();
pq.push({
char: null,
freq: left.freq + right.freq,
left,
right,
});
}
return pq.pop();
}
function generateCodes(root: HuffmanNode): Map<string, string> {
const codes = new Map<string, string>();
function dfs(node: HuffmanNode | null, code: string): void {
if (!node) return;
if (node.char !== null) {
// 單字元時給 '0' 以確保有效編碼
codes.set(node.char, code || '0');
return;
}
dfs(node.left, code + '0');
dfs(node.right, code + '1');
}
dfs(root, '');
return codes;
}
function huffmanEncoding(text: string): { encoded: string; codes: Map<string, string> } {
// 統計字元頻率
const freqMap = new Map<string, number>();
for (const ch of text) freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1);
const root = buildHuffmanTree(freqMap);
const codes = generateCodes(root);
const encoded = text.split('').map(ch => codes.get(ch)!).join('');
return { encoded, codes };
}
// 測試
const { encoded, codes } = huffmanEncoding('abracadabra');
console.log('Codes:', Object.fromEntries(codes));
// 輸出：{ a: '0', b: '10', r: '110', c: '1110', d: '1111' }（依頻率而定）
console.log('Encoded length:', encoded.length);
// 輸出：比固定 3-bit 編碼（33 bits）更短
6. 分割字串（Partition Labels，LC 763）
將字串盡可能分割成多個片段，使每個字母只出現在一個片段中，回傳每個片段的長度。
function partitionLabels(s: string): number[] {
// 記錄每個字母最後出現的位置（決定片段邊界的關鍵）
const lastIndex = new Map<string, number>();
for (let i = 0; i < s.length; i++) {
lastIndex.set(s[i], i);
}
const result: number[] = [];
let start = 0; // 當前片段的起始位置
let end = 0; // 當前片段的最遠延伸位置
for (let i = 0; i < s.length; i++) {
// 若當前字元的最後出現位置超過 end，延伸當前片段
end = Math.max(end, lastIndex.get(s[i])!);
// 到達當前片段末尾，切割並記錄長度
if (i === end) {
result.push(end - start + 1);
start = i + 1;
}
}
return result;
// 時間：O(n)，空間：O(1)（字母表大小固定 26）
}
// 測試
console.log(partitionLabels('ababcbacadefegdehijhklij'));
// 輸出：[9, 7, 8]
console.log(partitionLabels('eccbbbbdec'));
// 輸出：[10]
C++ 對照
C++ 版本使用 STL 的 sort、priority_queue 與結構化綁定（C++17），展示與 TypeScript 版本的對應關係。
活動選擇
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int>> activitySelection(vector<pair<int,int>>& intervals) {
// 按結束時間升序排列
sort(intervals.begin(), intervals.end(),
[](const pair<int,int>& a, const pair<int,int>& b) {
return a.second < b.second;
});
vector<pair<int,int>> result;
int lastEnd = INT_MIN;
for (auto& [start, end] : intervals) {
if (start >= lastEnd) {
result.push_back({start, end});
lastEnd = end;
}
}
return result;
}
Huffman 編碼
#include <queue>
#include <unordered_map>
#include <string>
#include <memory>
#include <functional>
using namespace std;
struct HuffNode {
char ch;
int freq;
shared_ptr<HuffNode> left, right;
HuffNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
struct Compare {
bool operator()(const shared_ptr<HuffNode>& a, const shared_ptr<HuffNode>& b) {
return a->freq > b->freq; // Min-Heap：頻率小的優先
}
};
unordered_map<char, string> huffmanCodes(const string& text) {
unordered_map<char, int> freq;
for (char c : text) freq[c]++;
priority_queue<shared_ptr<HuffNode>,
vector<shared_ptr<HuffNode>>,
Compare> pq;
for (auto& [ch, f] : freq)
pq.push(make_shared<HuffNode>(ch, f));
while (pq.size() > 1) {
auto left = pq.top(); pq.pop();
auto right = pq.top(); pq.pop();
auto merged = make_shared<HuffNode>('\0', left->freq + right->freq);
merged->left = left;
merged->right = right;
pq.push(merged);
}
// 生成編碼（DFS 遍歷 Huffman 樹）
unordered_map<char, string> codes;
function<void(shared_ptr<HuffNode>, string)> dfs = [&](
shared_ptr<HuffNode> node, string code) {
if (!node) return;
if (node->ch != '\0') { codes[node->ch] = code; return; }
dfs(node->left, code + "0");
dfs(node->right, code + "1");
};
dfs(pq.top(), "");
return codes;
}
跳躍遊戲 II
#include <vector>
#include <algorithm>
using namespace std;
int jump(vector<int>& nums) {
int n = nums.size();
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < n - 1; i++) {
farthest = max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
if (currentEnd >= n - 1) break;
}
}
return jumps;
}
加油站
#include <vector>
using namespace std;
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totalGas = 0, currentGas = 0, startStation = 0;
int n = gas.size();
for (int i = 0; i < n; i++) {
int net = gas[i] - cost[i];
totalGas += net;
currentGas += net;
if (currentGas < 0) {
startStation = i + 1;
currentGas = 0;
}
}
return totalGas >= 0 ? startStation : -1;
}
分數背包（Fractional Knapsack）
#include <vector>
#include <algorithm>
using namespace std;
struct Item {
double weight, value;
double ratio() const { return value / weight; }
};
double fractionalKnapsack(vector<Item>& items, double capacity) {
// 按單位價值（value/weight）降序排列
sort(items.begin(), items.end(),
[](const Item& a, const Item& b) {
return a.ratio() > b.ratio();
});
double totalValue = 0.0;
for (auto& item : items) {
if (capacity <= 0) break;
if (item.weight <= capacity) {
// 整個物品都能放入
totalValue += item.value;
capacity -= item.weight;
} else {
// 只能放一部分（分數背包的關鍵操作）
totalValue += item.ratio() * capacity;
capacity = 0;
}
}
return totalValue;
}
複雜度分析表
| 演算法 | 時間複雜度 | 空間複雜度 | 貪心策略 |
|---|---|---|---|
| 活動選擇 | O(n log n) | O(1) | 按結束時間排序，選最早結束的不重疊活動 |
| Huffman 編碼 | O(n log n) | O(n) | Min-Heap 取兩最小頻率合併 |
| 分發餅乾（LC 455） | O(n log n) | O(1) | 最小能滿足配最小孩子 |
| 跳躍遊戲（LC 55） | O(n) | O(1) | 維護最遠可達位置 |
| 跳躍遊戲 II（LC 45） | O(n) | O(1) | 區間 BFS，每層覆蓋最遠 |
| 加油站（LC 134） | O(n) | O(1) | 候選起點跳過不可行區段 |
| 分割字串（LC 763） | O(n) | O(1) | 字母最後出現位置決定邊界 |
| 分數背包 | O(n log n) | O(1) | 按單位價值排序，優先取高值密度物品 |
變體與延伸
分數背包（Fractional Knapsack）
與 0/1 背包（需 DP）不同，分數背包允許取物品的一部分（如液體、穀物）。貪心策略：按**單位重量的價值（value/weight）**降序排列，依序取物，容量不足時取一部分。
為什麼分數背包可以貪心，0/1 背包不行？
分數背包的貪心選擇性質成立：取單位價值最高的物品不會後悔，因為任何剩餘空間都能以最高可得單位價值填滿，不存在「留著容量給後來物品」更好的情況。0/1 背包中取了某物品後容量固定減少，可能導致更高價值的組合無法達成——需要窮舉所有子集（DP）。
function fractionalKnapsack(
items: { weight: number; value: number }[],
capacity: number
): number {
// 按單位價值降序排列
items.sort((a, b) => b.value / b.weight - a.value / a.weight);
let totalValue = 0;
for (const item of items) {
if (capacity <= 0) break;
if (item.weight <= capacity) {
// 整個物品放入
totalValue += item.value;
capacity -= item.weight;
} else {
// 只取部分（分數背包的關鍵：允許切割）
totalValue += (item.value / item.weight) * capacity;
capacity = 0;
}
}
return totalValue;
}
// 測試：items=[{w:10,v:60},{w:20,v:100},{w:30,v:120}]，capacity=50
const items = [
{ weight: 10, value: 60 }, // 單位價值 6.0
{ weight: 20, value: 100 }, // 單位價值 5.0
{ weight: 30, value: 120 }, // 單位價值 4.0
];
console.log(fractionalKnapsack(items, 50));
// 輸出：240（取全部 w=10, w=20 和一半 w=30 的物品）
最小生成樹：Kruskal 與 Prim 簡介
最小生成樹（Minimum Spanning Tree，MST）問題也是貪心的經典應用領域：
Kruskal 演算法：按邊的權重升序排序，貪心選取不形成環的最小邊，利用 Union-Find 偵測環。時間複雜度 O(E log E)，適合稀疏圖。
Prim 演算法：從任意節點出發，每步貪心選取連接「已選集合」與「未選集合」之間的最小權重邊。使用 Min-Heap 實現時間複雜度 O((V+E) log V)，適合稠密圖。
兩者均依賴割定理（Cut Property）：對圖的任意割（Cut），跨越割的最小權重邊一定屬於某個 MST。這就是這兩個演算法正確性的理論基礎，也是貪心在圖論中最漂亮的應用之一。
面試考點：貪心 vs DP 判斷框架
許多面試官會刻意設計「看起來像貪心，其實需要 DP」或反過來的題目。以下是判斷框架：
使用貪心的信號
- 問題有明確的排序維度：「按結束時間」、「按大小」、「按單位價值」等
- 局部選擇不影響後續可選集合的「品質」：選完當前最優，剩下的問題結構不變
- 交換論證能成立：用貪心選擇替換最優解中的非貪心選擇，結果不變差
使用 DP 的信號
- 選擇之間有「後效性」：當前選擇影響後續哪些選擇可用
- 局部最優不等於全域最優：能找到一個反例
- 問題問的是「組合計數」或「恰好等於某值的方案數」
具體判斷流程：
問題 → 能否找到貪心準則？
↓ 是
嘗試交換論證：替換貪心選擇後，答案不差？
↓ 是 ↓ 否
用貪心 用 DP（重疊子問題+最優子結構）
貪心 vs DP 對比表：
| 維度 | 貪心 | 動態規劃 |
|---|---|---|
| 決策方式 | 每步選當前最優，不回頭 | 考慮所有子問題的最優組合 |
| 子問題數量 | 只解一個（當前貪心後的子問題） | 解所有子問題 |
| 時間效率 | 通常 O(n log n) 或 O(n) | 通常 O(n²) 或 O(n·k) |
| 正確性保證 | 需要嚴格證明（交換論證） | 狀態轉移方程正確則保證最優 |
| 典型題型 | 區間排程、Huffman、跳躍遊戲 | 背包問題、最長公共子序列、矩陣鏈乘法 |
LeetCode 練習
| 題號 | 題目 | 難度 | 貪心策略 |
|---|---|---|---|
| 455 | Assign Cookies | Easy | 排序後雙指標，最小餅乾配最小孩子 |
| 55 | Jump Game | Medium | 維護最遠可達位置，判斷是否能到終點 |
| 134 | Gas Station | Medium | 全局總油量判斷有無解，局部負值跳過起點 |
| 435 | Non-overlapping Intervals | Medium | 按結束時間排序，貪心移除最少區間 |
| 763 | Partition Labels | Medium | 字母最後出現位置決定片段邊界 |
LC 435 — 無重疊區間（Non-overlapping Intervals）：
本題與活動選擇互為鏡像：求最少移除幾個區間使其餘區間不重疊，等同於求最多保留幾個不重疊區間，再用總數相減。
function eraseOverlapIntervals(intervals: number[][]): number {
if (intervals.length === 0) return 0;
// 按結束時間升序排列（活動選擇的核心排序方式）
intervals.sort((a, b) => a[1] - b[1]);
let count = 1; // 最多保留的不重疊區間數
let lastEnd = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= lastEnd) {
// 不重疊，選取此區間
count++;
lastEnd = intervals[i][1];
}
// 重疊，跳過（即「移除」此區間）
}
return intervals.length - count; // 需要移除的數量
}
// 測試
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 輸出：1
console.log(eraseOverlapIntervals([[1,2],[1,2],[1,2]])); // 輸出：2
常見陷阱
學習貪心演算法時，有幾個高頻錯誤值得特別注意：
忘記排序：絕大多數貪心問題需要先對輸入排序（按結束時間、按大小、按比率等），未排序直接貪心幾乎必錯。活動選擇、分發餅乾、分數背包都依賴排序作為前提。
貪心選擇依據錯誤：活動選擇問題中，按「開始時間最早」或「持續時間最短」貪心均是錯的，只有「結束時間最早」才能保證全域最優。選擇貪心標準時務必做交換論證驗證。
對 0/1 問題套用分數背包貪心：分數背包貪心正確，但 0/1 背包（物品不可分割）使用同樣的貪心策略會得到錯誤答案。判斷依據：物品能否分割？
加油站問題忽略無解情況：程式在
totalGas < 0時需返回-1而非任意值。遺漏此檢查在無解情況下會回傳錯誤的起點索引。Huffman 單字元輸入未處理：若輸入只有一種字元（如
"aaaa"），優先佇列中只剩一個節點無法合併，需特判並給予編碼'0'。
總結
貪心演算法的核心魅力在於它的「無畏」——每步都拿當前最好的，從不回頭。這種簡單的策略在滿足貪心選擇性質與最優子結構的問題上，能以 O(n log n) 甚至 O(n) 的極高效率取得最優解。
本文涵蓋的核心要點：
- 兩個充分條件：貪心選擇性質 + 最優子結構，缺一不可
- 交換論證法：證明貪心正確性的標準工具，假設替換再驗證不損失最優性
- 六個經典實作：活動選擇、分發餅乾、跳躍遊戲（I/II）、加油站、Huffman 編碼、分割字串
- 貪心 vs DP 判斷框架：能交換論證 → 貪心；有後效性或需組合計數 → DP
下一篇將探討分治法（Divide and Conquer）——另一個將大問題切分為小問題的核心策略，與貪心在「子問題處理方式」上形成鮮明對比。歡迎持續關注！
如有任何問題或疑惑，歡迎透過 聯絡頁面 與我交流。