一、貪心算法的基本概念

定義：貪心算法是指在求解問題時，每一步都選擇當前狀態下的最優解（局部最優），從而希望最終達到全局最優的算法策略。其核心思想是“目光短淺”，不考慮整體影響，僅關注當前步驟的最佳選擇。

二、貪心算法的適用條件

貪心算法并非對所有問題有效，需滿足以下性質：

1. 貪心選擇性質：問題的全局最優解可以通過一系列局部最優選擇達到。
2. 最優子結構：問題的最優解包含子問題的最優解。

三、貪心算法的設計步驟

1. 確定問題的最優子結構：分析問題是否可分解為子問題，且子問題的最優解構成全局最優解。
2. 定義貪心策略：確定每一步選擇的“最優”標準（如最小代價、最大收益、最短距離等）。
3. 證明策略正確性：通過數學歸納法或反證法證明局部最優選擇可推導出全局最優解（關鍵難點）。
4. 實現算法：根據策略設計具體步驟，通常結合數據結構（如優先隊列、排序）優化效率。

四、貪心算法的經典應用場景

1. 區間調度問題

• 問題描述：給定多個區間，選擇不重疊的最大區間集合。
• 貪心策略：按區間結束時間排序，每次選結束時間最早的區間，確保剩余時間最大化。
• 示例：活動選擇問題（LeetCode 435. 無重疊區間）。

2. 背包問題

• 0-1背包（不適用貪心）：物品不可分割，需用動態規劃（貪心可能選到總價非最優的組合）。
• 分數背包（適用貪心）：物品可分割，按“單位重量價值”從高到低選擇，填滿背包。
• 策略：性價比 = 價值/重量，優先選性價比高的物品。

3. 最小生成樹（MST）

• Kruskal算法：按邊權從小到大選邊，用并查集避免環，直到連通所有節點（貪心選最小邊）。
• Prim算法：從任意節點出發，每次選連接當前樹與未連接節點的最小邊（貪心選最小邊）。

4. 單源最短路徑（Dijkstra算法）

• 策略：維護各節點到源點的最短距離，每次選距離最小的未訪問節點，更新其鄰接節點的距離（貪心選當前最短路徑）。
• 前提：圖中邊權非負，否則需用Bellman-Ford算法。

5. 霍夫曼編碼

• 目標：為字符生成最優前綴編碼，使編碼總長度最短。
• 策略：按字符頻率構建霍夫曼樹，頻率低的字符分配較長編碼，頻率高的分配較短編碼（貪心選頻率最小的兩個節點合并）。

6. 零錢兌換

• 問題：用最少硬幣數湊出金額amount（若硬幣面值滿足“貪心性質”，如1、5、10、25）。
• 策略：每次選不超過剩余金額的最大面值硬幣。
• 注意：若面值不滿足貪心性質（如1、3、4，湊6時貪心選4+1+1，實際最優為3+3），需用動態規劃。

五、貪心算法的正確性證明方法

1. 交換論證法：假設存在一個最優解與貪心解不同，通過交換兩者的部分選擇，證明貪心解可以轉化為最優解，且不會更差。
2. 數學歸納法：證明對于所有子問題，貪心策略能得到最優解，進而推導出全局最優。
3. 反證法：假設貪心策略不能得到最優解，推導出矛盾，從而證明策略的正確性。

六、貪心算法與動態規劃的對比

特性	貪心算法	動態規劃
決策方式	只看當前最優（局部最優）	考慮所有可能，記錄子問題解
時間復雜度	通常更低（O(n logn)或O(n)）	通常更高（O(n2)或O(nk)）
適用場景	滿足貪心選擇性質和最優子結構	需考慮子問題重疊和最優子結構
經典問題	區間調度、Kruskal、Dijkstra	0-1背包、最長公共子序列

七、貪心算法的經典例題與解法

1. 跳躍游戲（LeetCode 55）

• 問題：給定數組nums，nums[i]表示從位置i可跳躍的最大距離，判斷是否能到達最后一個位置。
• 貪心策略：維護當前能到達的最遠位置max_reach，遍歷數組時更新max_reach，若當前位置超過max_reach則失敗。
• 代碼思路：

  def canJump(nums):max_reach, n = 0, len(nums)for i in range(n):if i > max_reach:  # 無法到達當前位置return Falsemax_reach = max(max_reach, i + nums[i])if max_reach >= n - 1:  # 提前到達終點return Truereturn True
  

2. 分發餅干（LeetCode 455）

• 問題：每個孩子有需求值g[i]，每個餅干有大小s[j]，求最多能滿足多少孩子（孩子得到的餅干需≥需求）。
• 貪心策略：將g和s排序，每次用能滿足當前孩子的最小餅干（避免浪費大餅干）。
• 代碼思路：

  def findContentChildren(g, s):g.sort()s.sort()i = j = 0while i < len(g) and j < len(s):if s[j] >= g[i]:  # 餅干滿足孩子需求i += 1j += 1return i
  

3. 檸檬水找零（LeetCode 860）

• 問題：檸檬水5元，顧客付5、10、20元，求能否給所有顧客正確找零。
• 貪心策略：優先用大面值零錢找零（但需保留足夠的5元給后續顧客）。
• 實現：記錄5元和10元的數量，付20元時優先用10+5，其次用3張5元。

4. 加油站（LeetCode 134）

• 問題：環形路線上有n個加油站，每個加油站有油量gas[i]，從i到i+1需消耗cost[i]，求是否存在起點繞一圈。
• 貪心策略：若總油量≥總消耗，則必存在解；遍歷加油站，當累計油量為負時，重置起點為下一個加油站。

八、貪心算法的陷阱與注意事項

1. 局部最優≠全局最優：貪心策略可能在某些情況下失效（如零錢兌換問題中的非貪心面值），需先證明策略正確性。
2. 策略選擇的多樣性：同一問題可能有多種貪心策略，需選擇能導向全局最優的策略（如區間調度按結束時間排序比按開始時間更優）。
3. 結合數據結構優化：優先隊列（堆）、排序、哈希表等常與貪心算法結合，提升效率（如Dijkstra用優先隊列優化）。

九、貪心算法的核心思想總結

貪心算法的本質是通過“短視”的局部最優選擇，逐步構建全局最優解，其優勢在于實現簡單、效率高，但適用范圍受限于問題的貪心性質。在實際應用中，需先分析問題是否滿足貪心條件，再設計策略并驗證正確性。對于不滿足條件的問題，動態規劃或回溯算法可能是更優的選擇。