一、什么是贪心？
重点：贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
举例说明：
有一堆钞票，你可以拿走十张，如果想要拿到最大的金额，你会怎么拿?
每次拿最大的，最终结果就是拿走最大金额。
每次拿最大的就是局部最优，最后拿走最大金额就是推出全局最优。
二、什么时候用贪心（套路）
没有固定的套路，唯一的难点就是如何通过局部最优，推出整体最优。
那么怎么才能看出局部最优是否能推出整体最优？
也没有！靠直接手动模拟，如果模拟可行就可以试一试贪心策略，如果不可行，可能需要动态规划。
如何验证可不可以用贪心算法？
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心。
三、贪心一边解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出合适的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
版权声明：本文为weixin_47683560原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。