贪心法
灵魂拷问
什么是贪心算法（Greedy Algorithm）？
什么是贪心选择性质？
如何证明贪心算法的正确性？
动态规划和贪心算法的区别是什么？
贪心概念
适用于最优化问题的算法往往包含一系列步骤，每一步都包含若干选择。贪心算法总是做出在当前看来是最好的选择。
贪心算法的基本要素：
（1）最优子结构性质：通过贪心选择可以将问题转移到子问题上，原始问题最优解=贪心选择+子问题的最优解
（2）贪心选择性质：全局最优解可以通过局部最优选择得到
贪心法的设计
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优，推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？
不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢？
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
贪心一般解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。
做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。
重要的贪心算法
