贪心算法Greedy

在对问题求解时，总是做出在当前看来是最好的选择

使用贪心算法的时候，为了凑出36元，每次都选择最大面值的纸币；这个图中的例子不是很恰当，比如我们如果为了凑出18元，有10，9，1三种面值的钞票，贪心算***选择1张10元的和8张1元的，而其实用两张9元的即可得到

适用Greedy的场景

简单地说，问题能够分解成为子问题来解决，子问题的最优解能够递推到最终问题的最优解。这种子问题最优解成为最优子结构。

贪心算法与动态规划的不同在于他对于每个子问题的解决方案都做出选择，不能回退。动态规划会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。