Greedy Algorithm

貪婪演算法（Greedy Algorithm）是一種在每個決策階段都採取當前狀態下最好或最佳（局部最優）的選擇，希望最後拼湊出全體最佳（全局最優）結果的策略。

它最大的特點是直觀、簡單且執行速度快，但並不保證所有問題都能找到絕對的全體最佳解，對範圍相當廣泛的許多問題它能產生整體最優解或者是整體最優解的近似解。

白話理解

想像你身上只帶了幾張大鈔要找零錢，每次都優先拿「面額最大、但不超過剩餘金額」的鈔票或硬幣。這種「每一步都選當下看起來最划算的選項，選完就不回頭」的做法，就是 Greedy 的精神。

核心概念

• 局部最優：每一個步驟都只看眼前最有利的選擇。
• 絕不回頭：做出的決策不會被重新考慮或改變。
• 性質需求：通常需要問題本身具備「最佳子結構」與「貪婪選擇性質」才能得到正確答案。

範例

直接以 Leetcode 題目作為範例說明。

題目：在陣列的第一格，每一格的數字代表你最多可以往後跳幾步，問能不能到達最後一格

Example 1:
Input: nums = [2,3,1,1,4]
Output: true

Example 2:
Input: nums = [3,2,1,0,4]
Output: false

Python

def can_jump(nums):
    n = len(nums)
    far_idx = 0  # 記錄最遠可以到哪一個 index

    for i in range(n):
        if far_idx < i:  # 檢查最遠可到的 index 可否到當下這裡
            return False
        far_idx = max(far_idx, i + nums[i])  # 貪婪的重點：每次只取最遠可以到哪

    return far_idx >= n - 1

JavaScript

var canJump = function(nums) {
    const n = nums.length
    let farIdx = 0      // 記錄最遠可以到哪一個 index

    for (let i = 0; i < n; i++) {
        if (farIdx < i) return false            // 檢查最遠可到的 index 可否到當下這裡
        farIdx = Math.max(farIdx, i + nums[i])  // 貪婪的重點：每次只取最遠可以到哪
    }

    return farIdx >= n - 1
};

Java

class Solution {
    public static boolean canJump(int[] nums) {
        int n = nums.length;
        int farIdx = 0;      // 記錄最遠可以到哪一個 index

        for (int i = 0; i < n; i++) {
            if (farIdx < i) return false;                 // 檢查最遠可到的 index 可否到當下這裡
            farIdx = Math.max(farIdx, i + nums[i]);       // 貪婪的重點：每次只取最遠可以到哪
        }

        return farIdx >= n - 1;
    }
}

逐步拆解：以 nums = [2, 3, 1, 1, 4] 為例

i	nums[i]	farIdx（走這步前）	i + nums[i]	farIdx（更新後）	說明
0	2	0	0 + 2 = 2	2	站在第 0 格，最遠能跳到第 2 格
1	3	2	1 + 3 = 4	4	站在第 1 格，發現跳到第 4 格更遠，貪婪地更新紀錄
2	1	4	2 + 1 = 3	4（不變）	3 沒有比 4 遠，維持原紀錄
3	1	4	3 + 1 = 4	4（不變）	同樣沒有更遠，維持原紀錄
4	4	4	-	-	i 已經走到最後一格（n - 1 = 4），且 farIdx >= 4，回傳 true

全程只掃過一次陣列（O(n)），因為 Greedy 完全不回頭檢查「如果剛才選別的會不會更好」，所以速度非常快。

為什麼 Greedy 不一定對？

Greedy 只看「當下」最好的選擇，並不會考慮「這個選擇會不會害後面的步驟變差」。如果問題不具備「貪婪選擇性質」，走一步算一步反而會導致錯誤答案。

舉例：找零錢問題，如果硬幣面額是 [1, 3, 4]，要利用最少硬幣湊出 6 元：

• Greedy 做法：優先拿最大面額 → 拿一個 4，剩 2 元，再拿兩個 1 元 → 總共用了 3 枚硬幣（4+1+1）。
• 但其實最佳解是兩個 3 元 → 只需要 2 枚硬幣（3+3）。

這個例子中，「每次都拿最大面額」這個局部最優的選擇，並沒有帶來全局最優的結果。像這類「每一步的選擇會互相影響、需要綜合考慮所有可能」的問題，通常要改用 Dynamic Programming 才能保證找到正解。

Greedy vs Dynamic Programming

兩者都是把大問題拆成一步一步的決策，但思考方式完全不同：

比較項目	Greedy	Dynamic Programming
決策方式	每一步只看當下最好的選擇，選完不回頭	會考慮所有可能的選擇，並記錄每個子問題的最佳解
是否保證最佳解	不一定，只在問題具備「貪婪選擇性質」時才保證正確	只要問題具備「最佳子結構」與「重疊子問題」，就保證找到最佳解
執行速度 / 空間	通常較快，額外空間需求低	通常較慢，需要額外空間記錄子問題的解
適合場景	找零錢（面額為特定倍數關係時）、Jump Game、Interval Scheduling	背包問題、最長共同子序列、找零錢（一般情況）

新手小提醒

拿到題目時，可以先想想看「如果我每一步都選當下最好的，最後結果會不會被前面的選擇拖累？」。
如果答案是「有可能」，代表這題不能單純用 Greedy，需要考慮所有選擇的 DP，或是需要證明貪婪選擇性質確實成立。

適用情況

• 區間排程問題（Interval Scheduling）：例如選出最多不重疊的會議時段，每次都貪婪選擇「結束時間最早」的活動。
• 最小生成樹（Minimum Spanning Tree）：Kruskal's Algorithm、Prim's Algorithm 都是每一步貪婪選擇目前權重最小的邊。
• 跳躍 / 覆蓋類問題：例如 Jump Game，每一步都貪婪地記錄「目前能到達的最遠位置」。
• 面額具備特定倍數關係的找零問題：例如台幣、美金這類面額設計良好的貨幣系統，貪婪法通常能找到最少硬幣數的解。

常見誤區

• 看到「求最大/最小值」就直覺套用 Greedy：Greedy 只適合能證明「局部最優 = 全局最優」的問題，不是所有最佳化問題都適用。
• 沒有驗證貪婪選擇是否正確就直接寫程式：建議先用小範例（像上面找零錢的例子）手動驗證邏輯是否合理，再動手實作。
• 和 Dynamic Programming 搞混：如果不確定局部最優是否等於全局最優，通常改用 DP 會比較保險。