# 贪心算法简介
贪心算法又称「贪婪算法」。
- 在对问题求解时，总是做出在当前看来最好的选择。即贪心算法不从整体最优上加以考虑；
- 贪心算法所作出的是在某种意义上的局部最优解。
贪心算法和动态规划算法都是由局部最优导出全局最优，二者的区别如下。
# 贪心算法
- 贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留；
- 贪心法正确的前提是：每一步的最优解一定包含上一步的最优解。
# 动态规划
- 全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解；
- 动态规划的关键是确定「状态转移方程」，即如何通过已经求出的局部最优解推导出全局最优解；
- 边界条件：即最简单的，可以直接得出的局部最优解。
# 重点概括
- 可以使用贪心算法解决问题一般都需要严格的理论证明，但是一般面试和笔试对严格证明要求不高，所以面对一个问题，有「贪心算法」的直觉比较重要；
- 贪心算法可以和动态规划算法进行比较，动态规划每一步需要求解所有的子问题，并且从中选择一个最优解。可以使用贪心算法解决问题，每一步只需要求解其中一个子问题，因此可以使用贪心算法解决的问题，时间复杂度一般为线性级别。
作者：liweiwei1419 链接：https://suanfa8.com/greedy 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。