Greedy 模板

──────────────────────────────────────────────────────────────────────

Greedy 沒有一段可以照抄的 code。它是一個判斷：這一題能不能省掉搜尋，每一步直接選一個答案就往下走。

貪在哪裡

同一個問題，DP 和 Greedy 的差別不在答案，在決定的時機：

DP — 每一步把所有分支展開，用記憶化避免重算，最後才知道哪條路最好
Greedy — 證明每一步只有一個分支值得走，所以連展開都不用

所以 Greedy 可以看成 DP 的退化情形：決策樹每層只剩一個分支。「貪」指的是當下就把最好的拿走，而且不回頭。

為什麼一定要證明

局部最優不等於全域最優。最乾淨的反例是找零錢：

coins = [1, 3, 4], amount = 6

貪心：拿 4 → 剩 2 → 拿 1 → 拿 1    共 3 枚
最佳：3 + 3                       共 2 枚

貪心在第一步就把 4 拿走，而 4 這個選擇讓剩下的 2 只能用兩個 1 湊。這就是為什麼 322. Coin Change 是 DP 不是 Greedy。

「拿最大的」本身沒有任何保證。 一題能不能貪，跟你多想拿到最大值無關，跟問題的結構有關。

交換論證

要證明能貪，用的幾乎都是同一招：

假設有一個最佳解沒有採用我這一步的選擇。把它換成我的選擇，證明答案不會變差。既然不會變差，那「包含我的選擇」的最佳解一定存在。

實際上會長成三種形狀。

一、排序後永遠選最早結束的

intervals.sort(key=lambda x: x[1])   # 按結束時間，不是開始時間
end = float('-inf')
count = 0
for start, finish in intervals:
    if start >= end:                 # 不重疊才拿
        count += 1
        end = finish

交換論證：最早結束的那個留給後面的空間最大。把它換成任何一個結束更晚的，可選的區間只會變少不會變多。

排序的 key 選錯就整題錯，這是這類題唯一的難點 —— 而且端點相接算不算重疊要看題目（435 算不重疊，452 算重疊），差在 >= 還是 >。

例題：435. Non-overlapping Intervals、452. Minimum Number of Arrows、1024. Video Stitching、253. Meeting Rooms II

二、對撞時丟掉不可能更好的一邊

left, right = 0, len(height) - 1
while left < right:
    ans = max(ans, min(height[left], height[right]) * (right - left))
    if height[left] < height[right]:
        left += 1        # 矮的那邊不可能再參與更好的答案
    else:
        right -= 1

交換論證：不管移動哪一邊，底邊都一定變短；而水位不可能超過現在較矮的那根。兩個因子都不可能變好，所以矮的那根可以安全丟掉。

這一類的貪心動作是丟棄而不是選取 —— 每一步安全地砍掉一個候選。

例題：11. Container With Most Water、870. Advantage Shuffle

三、每次取極值（配 heap）

當「最好的選擇」會隨著每一步改變，就用 heap 動態維護：

heapq.heapify(sticks)
while len(sticks) > 1:
    a = heapq.heappop(sticks)
    b = heapq.heappop(sticks)
    heapq.heappush(sticks, a + b)    # 合併後放回去，重新參與競爭

交換論證：先合併的成本會被後面每一次合併重複計入，所以短的一定要先合併。

訊號是「排序一次不夠，因為選過之後順序會變」 —— 這時候 heap 才是對的資料結構，而不是先 sort()。

例題：1167. Minimum Cost to Connect Sticks、1046. Last Stone Weight、1962. Remove Stones to Minimize the Total

是 Greedy，還是只是「排序 + 掃一遍」

這兩件事長得很像，但只有前者需要證明：

	有沒有在做選擇	例子
是 Greedy	有候選被選中或被丟棄，選了就回不去	435、11、122、134
不是	每個元素都會被處理，輸出是被決定的	56. Merge Intervals、57. Insert Interval、986. Interval List Intersections

56 沒有選擇 —— 它只是把資料換一種形狀輸出，所以它不需要交換論證，也不會有「貪錯」的風險。

同樣的道理解釋了股票家族的分界：121 只是在算前綴最小值，不是貪心；122 每天在決定「這段漲幅吃不吃」，才是。

換了名字的貪心

有些演算法本質是貪心，只是有自己的名字，通常不會掛 Greedy 這個標籤：

MST — Kruskal 每次挑最短的邊、Prim 每次挑最近的點，正確性靠 cut property，那就是交換論證。見 1584. Min Cost to Connect All Points、1135. Connecting Cities
Dijkstra — 每次確定距離最小的點就永不再改
Huffman — 就是上面第三種形狀

同一題的兩種寫法

這幾題 DP 和 Greedy 並排放最能看出差別：

題目	DP 版本	Greedy 版本
55. Jump Game	每個點問「從我出發能否到終點」， $O (n^{2})$	只維護「能到的最遠處」， $O (n)$
53. Maximum Subarray	`dp[i] = max(dp[i-1] + num, num)`	前綴為負就整段丟掉（Kadane）
2244. Minimum Rounds	記憶化拆解 2 和 3	直接算 $⌈ c / 3 ⌉$

共同的模式是：發現「怎麼走到這裡的」對後面沒有影響，狀態就從 $O (n)$ 塌成 $O (1)$ 。

怎麼判斷能不能貪

順序是這樣：

先花 30 秒找反例。 這比想證明快得多，而且大部分想貪的直覺會在這裡被打掉。
排序之後變簡單 → 通常可以貪。 區間題、任務排程題幾乎都是「先排序，再一路掃」。
選了之後剩下的問題跟原題同型 → 可以貪。 這是最佳子結構。
選擇會消耗「可互相取代的資源」→ 大概不能貪，要 DP。 找零錢就是這種：4 和 3+1 都是 4 塊錢，但對後續的影響完全不同，你在當下無從判斷。

最實用的一條分界線：

當「這一步選什麼」會改變「剩下能選什麼」的組合，就不能貪。

更多題目 → #Greedy

回到總索引 → Coding Interview Preparation