不会飞的章鱼

熟能生巧,勤能补拙;念念不忘,必有回响。

算法训练营-贪心的实现、特性及实战题目解析

贪心算法-Greedy

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。

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

  • 贪心:当下做局部最优判断
  • 回溯:能够回退
  • 动态规划:最优判断 + 回溯

可以解决的最优化问题

  • 求图中的最小生成树
  • 求哈夫曼编码等

由于贪心法的高效性以及所求得的答案比较接近最优结果,贪心算法可以用作辅助算法或直接解决一些要求结果不特别精确的问题。

适用贪心算法的场景

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

实战题目

leetcode-322.Coin Change

------ 本文结束------
如果本篇文章对你有帮助,可以给作者加个鸡腿~(*^__^*),感谢鼓励与支持!