第三章 贪心

1.概念

• 贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

贪心算法的使用前提：局部最优解一定能导致全局最优解。

例：有一堆钞票，你可以拿走十张，如果想达到最大的金额你要怎么拿？

2.解题步骤

1. 将问题分解为若干个子问题
2. 找出适合的贪心策略
3. 求解每一个子问题的最优解
4. 将局部最优解堆叠成全局最优解

• 使用贪心一定要证明，一般有两种方法：数学归纳法、反证法。
• 实际做题过程中，数学归纳较为麻烦，我们需要大胆假设，小心求证。找到一组反例 就可以推翻贪心！