概念
每一步尽可能实现当前的最优解
证明
贪心算法有两种证明方法：反证法和归纳法．一般情况下，一道题只会用到其中的一种方法来证明．
- 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了．
- 归纳法：先算得出边界情况（例如 n = 1）的最优解 F1，然后再证明：对于每个 n，F_{n+1} 都可以由 F_{n} 推导出结果．
区别
与动态规划的区别
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退．动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能．