贪心算法（Greedy Algorithm）
贪心算法（Greedy Algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
我们能够依据贪心法的2个重要的性质去证明：贪心选择性质和最优子结构性质。
贪心选择
什么叫贪心选择？从字义上就是贪心也就是目光短线。贪图眼前利益。在算法中就是仅仅依据当前已有的信息就做出选择，并且以后都不会改变这次选择**（这是和动态规划法的主要差别）**。
所以对于一个具体的问题。要确定它是否具有贪心选择性质，必须证明每做一步贪心选择是否终于导致问题的总体最优解。
最优子结构
当一个问题的最优解包括其子问题的最优解时，称此问题具有最优子结构性质。
运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。
基本思路
贪心算法的基本思路是从问题的某一个初始解触发一步一步地进行，根据抹个优化测度，每一步都要确保能获得局部最优解，每一步值考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连载一起不再是可行解时，就不把改数据添加到部分解中，知道把所有数据枚举玩，或者不能在添加算法停止。
过程
- 建立数学模型来描述问题；
- 把求解的问题分成若干个子问题；
- 对每一子问题求解，得到子问题的局部最优解；
- 把子问题的解局部最优解合成原来解问题的一个解。
贪心算法与动态规划
贪心算法往往是这种自顶向下的设计，先做出一个选择，然后再求解下一个问题，而不是自底向上解出许多子问题，然后再做出选择。
在做贪心选择时，我们直接做出当前问题中看起来最优的解，而不是考虑到子问题的解，这也是贪心算法和动态规划的不同之处，在动态规划中，我们往往每一个步骤都求做一个选择，这个选择往往依赖于子问题的解。而在贪心算法中，我们总是做出当时看来最佳的选择，然后再求解剩下唯一的子问题。贪心算法做出选择时可能会依赖于之前的选择或者子问题的解，但是绝对不依赖于将来的选择或者子问题的解。就是我们前面所说的，一个动态规划问题是自底向上的，而一个贪心算法问题是自顶向下的。
例子
LeetCode 的第 122 题 Best Time to Buy and Sell Stock II：
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
贪心算法，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，也就是说，只关心当前最优解，按照贪心策略，不关心以后，我们只关心当前利益。第0天买入，花费prices[0]，第一天卖出，得到prices[1]，那么我们的收获就是profit = prices[1] - prices[0]。那么有两种情况
（1）当profit > 0 时，赶紧买入卖出，能赚一笔是一笔。
（2）当profit <= 0 时，再买入卖出的话，那就是傻了，亏钱。
以此方式类推下去，即得最大利润。
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
int gain = prices[i] - prices[i - 1];
if (gain > 0) {
profit += gain;
}
}
return profit;
}
经典问题
活动时间安排的问题
贪心实例之线段覆盖（lines cover）
数字组合问题
找零钱的问题
在贪心算法里面最常见的莫过于找零钱的问题了，题目大意如下，对于人民币的面值有1元 5元 10元 20元 50元 100元，下面要求设计一个程序，输入找零的钱，输出找钱方案中最少张数的方案，比如123元，最少是1张100的，1张20的，3张1元的，一共5张！
解析：这样的题目运用的贪心策略是每次选择最大的钱，如果最后超过了，再选择次大的面值，然后次次大的面值，一直到最后与找的钱相等，这种情况大家再熟悉不过了，下面就直接看源代码：
Prim 算法 和 Kruskal 算法
Prim 算法 和 Kruskal 算法都是在加权无向图找到最小生成树的算法，它们也都是贪心算法。
哈夫曼编码
我们可以用 01 编码串来代表一个字符，例如 a 为 0，c 为 00，f 为 1100。这样，可能因为其中一个字符的编码是另一个字符的前缀而导致歧义。满足任何一个编码都不是另一个的前缀的编码被称为前缀码（Prefix Code）。
Reference
- 贪心算法详解 -https://blog.csdn.net/effective_coder/article/details/8736718
- 贪心算法 - https://juejin.im/post/5aea722e6fb9a07ac652dbc8
- 贪心算法 - http://staff.ustc.edu.cn/~lszhuang/alg/ch16.pdf
- 算法一篇通——贪心算法 - http://kyonhuang.top/greedy-algorithm/
- 【LeetCode】贪心算法–买卖股票的最佳时机 II（122） - https://segmentfault.com/a/1190000017907249
- leetcode刷题（一）：贪心算法 - https://zhuanlan.zhihu.com/p/57217890