前端之算法（八）贪心算法

大家好，今天我们要聊的是贪心算法这种方法，它和分而治之、动态规划一样，也是算法设计中的一种方法，你同样可以把它当作解决问题的一种思路。接下来让我来看看贪心算法是什么？

贪心算法

• 贪心算法是算法设计中的一种方法。

• 它期盼通过每个阶段的局部最优选择，从而达到全局的最优。

• 结果并不一定是最优。

这就像小时候不好好上学，天天玩，当时是开心了，但等长大了，找不到工作，结果就悲催了，这就是做了当前的最优选择，但是全局来看，并不是最优的。

在做算法题的过程中，我们同样可以用到贪心算法这种方法，但有时侯能得到最优解，有时候确又得不到最优解。

零钱兑换

接下来让我们来看一道算法题。它叫零钱兑换。

• 给定一个 coins 数组，里面存放了相应面值的零钱，

• 以及一个 amount 变量，需要兑换的钱总额。

• 结果需要输出兑换总额的最少数量

这个时候我们就可以通过贪心算法，先拿到局部最优解，也就是拿出零钱 5，在拿出零钱 5，再拿出 1，就可以得出全局最优解。

但是在另外一种情况下，我们就无法得出全局最优解了。

如果我们还是通过贪心算法，求局部最优解，先那一个 4，后面只能拿两个 1 了，输出 3，这显然 不是全局最优解。应该是拿出 两个 3，输出 2，这才是全局最优解。

所以贪心算法就不是局部最优解了。

说了这么多，其中不乏很多贪心算法的缺点，但是在有些题目中，贪心算法不失为一种很好的解决方法，所以，学习好贪心算法，对于我们的学习算法题，也是又很大的帮助的。

End~~