10.贪心算法Greedy
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最优利)的选择,从而希望导致结果是全局最好或最优的算法
贪心算法与动态规范不同点
贪心算法对每个子问题的解决方案都做出选择，不能回退 动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择，有回退功能
贪心法可以解决一些最优化问题, 如: 求图中的最小生成树、求哈夫曼编码等，然而对于功能和生活中的问题, 贪心法一般不能得到我们所要求的答案。
一旦一个问题可以通过贪心算法来解决, 那么贪心算法一般是解决这个问题的最好办法. 由于贪心法的高效性以及其所求得的答案比较接近最优结果,贪心法也可以用作辅助算法 或者直接解决一些要求结果不特别精确的问题。
适用贪心算法的场景
简单说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题 最优解称为最优子结构。
贪心算法与动态规划的不同在于他对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的 运算结果,并根据以前的结果对当前进行选择，有回退功能.