贪心算法学习随笔
这段时间刷算法题，最先上手的就是贪心。比起DP、回溯要考虑各种状态、记录大量中间数据，贪心写起来明显轻松很多。一开始我以为贪心万能，随便一道题都套“每次选最好的”思路，踩了好几次坑才明白，它有很明确的使用限制，不能凭直觉乱写。下面结合我做题时的真实思路和代码记录一下。
一、贪心到底是什么
它的核心逻辑很简单：处理问题时，每一步只选当下看起来最优的方案，选定之后不会回头修改，一路做到结束。
生活里找零钱、安排时间都自带这种思维。但这里有个关键前提：一步步的局部最优，最后合在一起必须是整体最优，不满足这个前提，答案一定会错。
二、入门例题：活动安排
题目要求同一时间只能参加一个活动，给出所有活动的起止时间，算出最多能参加几场。
我一开始试了两种思路，先按开始时间排序，结果安排到后面很容易被长活动占住时间；换成按结束时间从小到大排序后，每次挑结束最早的，剩下的空闲时间最多，能塞下更多活动，这才是正确局部策略。
importjava.util.*;classActivity{intstart,end;Activity(ints,inte){start=s;end=e;}}publicclassTest{publicstaticvoidmain(String[]args){List<Activity>acts=newArrayList<>();acts.add(newActivity(1,3));acts.add(newActivity(2,4));acts.add(newActivity(3,5));acts.add(newActivity(6,7));// 按结束时间升序acts.sort((a1,a2)->a1.end-a2.end);intcount=0;intlastEnd=-1;for(Activitya:acts){if(a.start>=lastEnd){count++;lastEnd=a.end;}}System.out.println(count);}}这段代码跑出来结果是3，是这组数据下能参加的最大数量。
三、零钱兑换，看清贪心的局限
标准人民币面额50、20、10、5、1，凑金额优先选大额，完全没问题。
publicclassCoin{publicstaticvoidmain(String[]args){int[]coins={50,20,10,5,1};inttarget=63;intcnt=0;intrest=target;for(intc:coins){if(rest>=c){cnt+=rest/c;rest=rest%c;}}System.out.println(cnt);}}但如果换一组特殊面额，比如只有1、3、4，凑6块钱。
按照贪心思路，先拿4，剩下两个1，一共3张；但最优解是两张3，只用两张。这里贪心就失效了。
做完这道题我才记牢：不是所有求最值的题都能用贪心，得先手动模拟小数据验证策略是否成立。
四、能用贪心的两个条件
- 贪心选择性：每一步最优的选择，最终能导向全局最优；
- 最优子结构：整个问题的最优解，包含子问题的最优解。
两个条件缺一个，贪心都不适用，要换成动态规划。
五、平时刷题常遇到的贪心题型
- 区间类：活动安排、区间覆盖，统一思路是排序后依次筛选；
- 分配类：分饼干、分糖果，两边排序后一一匹配；
- 数字构造：拼接数字求最大或最小值，自定义排序规则；
- 行程类：跳跃游戏、加油站，每一步选最远可到达位置。
六、贪心的优缺点
优点很明显，只需要一次排序加单层循环，运行速度快，代码量少，不用开数组存大量中间状态，调试起来简单。
缺点也很突出，适用场景窄，很多复杂问题满足不了贪心条件；而且正确性很难一眼看出来，必须手动举例验证，不能直接写代码。
学习小结
贪心算是入门最简单的算法，但也是最容易误用的。我之前做题总懒得验证策略，直接上手写代码，经常出现样例过了、测试数据出错的情况。
现在我自己固定一套做题流程：先想一种局部最优策略，手动用简单数字试一遍，确认能得到全局最优，再动手写代码；如果模拟后结果不对，直接放弃贪心，改用动态规划或者暴力枚举。
对比其他算法能明显感觉到，贪心不需要记录过往所有状态，走一步定一步，逻辑直白，但能不能用全看题目本身的特性。
