贪心算法 Greedy
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致
结果是全剧最好或最优的算法
贪心算法与动态规划的不同在于他对每个字问题的解决方案都做出选择，不能回退。动态规划则会
保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能
贪心算法可以解决工程中一些最优化问题， 如: 求图中的最小生成树、求哈夫曼编码等。然而对于 工程和生活中的问题，贪心法一般不能得到我们所要求的答案
一旦一个问题可以通过贪心法来解决。那么贪心法一般是解决这个问题的最好办法。 由于贪心法的搞笑性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者 直接解决一些要求结果不特别精确的问题
| 算法 | 特点 |
|---|---|
| 贪心 | 当下做局部最优判断 |
| 回溯 | 能够回退 |
| 动态规划 | 最优判断+回退 |
适用贪心算法的场景
简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 这种子问题最优解称为最优子结构
贪心算法与动态规划的不同在于它对每个子问题的解决方案都作出选择，不能回退。 动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
贪心的技巧
- 要能证明贪心可以得到全局最优解
- 贪心的角度 可能是从后往前，也可能是从某个局部开始贪心
leetcode
Coin Change 特别版本
一
当硬币可选集合固定 ： Coins = [20, 10, 5, 1]
求最少可以几个硬币拼出总数。比如 total = 36
前面的硬币是后面的硬币的二倍，每次用最大的即可。
二
贪心算法的反例
当硬币可选集合固定 ： Coins = [10, 9, 1]
求最少可以几个硬币拼出总数。比如 total = 18
最优解为 两个 9, 但是用贪心算法的话, 先用一个 10, 就要用 8 个 1