貪心演算法在每一步選擇當前最優的選項。關鍵在於證明局部最優能推導出全局最優。
Notes:
- 貪心不一定總是正確，需要驗證貪心選擇性質
- 常與排序結合使用
- 如果貪心不行，考慮用 DP
跨倉庫導讀#
- 對應理論章節：貪心演算法 ↗
#45
Jump Game II
#53
Maximum Subarray
#55
Jump Game
#134
Gas Station
#135
Candy
#646
Maximum Length of Pair Chain
#649
Dota2 Senate
#678
Valid Parenthesis String
#763
Partition Labels
#846
Hand of Straights
#918
Maximum Sum Circular Subarray
#978
Longest Turbulent Subarray
#1029
Two City Scheduling
#1423
Maximum Points You Can Obtain From Cards
#1647
Minimum Deletions to Make Character Frequencies Unique
#1871
Jump Game VII
#1899
Merge Triplets to Form Target Triplet
#1921
Eliminate Maximum Number of Monsters
#2439
Minimize Maximum of Array