贪心算法，在算法导论的引入中，把它认为是动态规划中的一种特例。所以它有优化子结构，但是它的子问题一个是空的，所以就只用求一个子问题。由此就从动态规划的框架中脱离出来，单独用方法来研究。具体贪心方法包括两个关键点，一是要有贪心选择性，二是具有优化子结构。

编辑中

贪心算法

两个核心要素：

1. 贪心选择性

   全局的优化解可以通过不断求局部最优解来获得。

2. 优化子结构

   优化问题的优化解包含子问题的优化解。

真是被贪心虐了。不知道怎么去证明贪心选择性和优化子结构。看了几个小时的贪心，依然找不到好的证明方法，看不太懂，简直要抓狂，啊…

贪心问题

1. 找最多的相容活动

2. Huffman编码

3. 最小生成树

4. 拟阵

5. 作业调度

6. Color a Tree .已知一颗树，每个节点上有权重$c_i$，给每个节点染色，从时间$t_0 = 0$开始，每个节点染色代价为$cost = c_t * t_i$ ， 且只有在其父亲节点被染色后才能被染色。每个节点染色耗时为1。求染色序列使代价最小。

7. n个石子，重量为$w_i$，聚集两堆石子的代价为两堆石子的代价和。求代价最小的聚集方式。

8. 环形公路，有n个加油站，每个加油站有油$gas[i]$，到达下一个加油站耗油$cost[i]$ ， 求一辆车从哪个加油站出发能够回到该出发的加油站。（设解唯一）

9. N个小朋友站成一排分糖。大家随机领到一个优先级，比相邻小朋友优先级高的小朋友领的糖应该也要比相邻小朋友多。最少一个小朋友发一颗糖。求最少发多少糖。

10. 有一个由非负整数构成的数组，每个值表示在该位置还能最多往前跳的步数。求从数组第一个位置出发，能否到达最后一个位置。

    如[3,2,1,1,4]就能够到达最后位置。

    [3,2,1,0,4]不能到达最后的位置。