贪心算法学习笔记

• 贪心算法学习笔记
  • 1，什么是贪心算法
  • 2，什么时候使用贪心算法
  • 3，贪心算法的解题步骤

1，什么是贪心算法

贪心算法就是以每次都选局部最优，以期望得出全局最优的算法。

2，什么时候使用贪心算法

问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就能用贪心算法的到最后的最优解。

3，贪心算法的解题步骤

贪心算法变化多端，没有具体的套路。但是可以有一种“心法”，即

1. 什么是局部最优？
2. 局部最优能否推导出全局最优？
3. 是否有明显的反例？

使用以上思路来思考。