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

发表于 2021-02-23 更新于 2022-05-06 分类于 Learn-Algorithms 阅读次数：
本文字数： 350 阅读时长 ≈ 1 分钟

贪心算法-Greedy

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

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

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

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