🪙 Greedy

每步取局部最優，並證明能達到全域最優。

19 題

📖 分類導讀

貪心演算法在每一步選擇當前最優的選項。關鍵在於證明局部最優能推導出全局最優。

Notes:

  • 貪心不一定總是正確，需要驗證貪心選擇性質
  • 常與排序結合使用
  • 如果貪心不行，考慮用 DP

兩個必要性質

貪心可行，需要問題同時具備：

  • 貪心選擇性質 (greedy choice property)：每一步取局部最優，不會斷送全局最優——也就是「當下最好的選擇」始終是某個全局最優解的一部分。
  • 最佳子結構 (optimal substructure)：做完這步貪心選擇後，剩下的子問題的最優解，加上這一步，就構成原問題的最優解。

貪心 vs DP

兩者都要求最佳子結構，差別在「要不要回頭」：

貪心動態規劃
決策當下直接挑最優，不反悔考慮所有子問題的解再合併
成本通常 O(n log n)（含排序）通常 O(n) 以上、需要狀態表
風險選擇性質不成立就會得到錯解較穩，但較慢、較耗空間

TIP

「所有能用貪心解的題，理論上都能用 DP 解；反之不然。」所以實戰策略是：先想想有沒有可證明的貪心；證不出來、或想到反例，就退回 DP。常見的貪心反例是「找零錢」在非標準幣值下會失敗。

跨倉庫導讀

#45Jump Game IIMedium★★★★★⏱ O(n)#53Maximum SubarrayMedium★★★★★⏱ O(n)#55Jump GameMedium★★★★★⏱ O(n)#134Gas StationMedium★★★★★⏱ O(n)#135CandyHard★★★★★⏱ O(n)#646Maximum Length of Pair ChainMedium★★★★★⏱ O(n log n)#649Dota2 SenateMedium★★★★★⏱ O(n)#678Valid Parenthesis StringMedium★★★★★⏱ O(n)#763Partition LabelsMedium★★★★★⏱ O(n)#846Hand of StraightsMedium★★★★★⏱ O(n log n)#918Maximum Sum Circular SubarrayMedium★★★★★⏱ O(n)#978Longest Turbulent SubarrayMedium★★★★★⏱ O(n)#1029Two City SchedulingMedium★★★★★⏱ O(n log n)#1423Maximum Points You Can Obtain From CardsMedium★★★★★⏱ O(n)#1647Minimum Deletions to Make Character Frequencies UniqueMedium★★★★★⏱ O(n + k log k)#1871Jump Game VIIMedium★★★★★⏱ O(n)#1899Merge Triplets to Form Target TripletMedium★★★★★⏱ O(n)#1921Eliminate Maximum Number of MonstersMedium★★★★★⏱ O(n log n)#2439Minimize Maximum of ArrayMedium★★★★★⏱ O(n)