打卡第27天------贪心算法
再次祈祷上帝，提前预备好自己，希望我可以在机会来临的时候，抓住机会，成功上岸！
一、理论基础
- 什么是贪心？
例如：有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
你肯定是每次拿最大的，最终结果就是拿走最大数额的钱了。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推导出的全局最优。
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。总结起来就是：通过局部最优，推导出全局最优，而且又举不出明显的反例。
- 贪心的套路(什么时候用贪心)
说句实话贪心算法并没有固定的套路。
一般数学证明有如下两种方法：
- 数学归纳法
- 反证法
贪心有时候就是常识性推导，所以会认为本应该就这么做。
- 贪心一般解题步骤：
贪心算法一般分如下四步：
- 将问题分解为若干个字问题；
- 找出合适的贪心策略；
- 求解每个子问题的最优解；
- 将局部最优解堆叠成全局最优解。
这四步其实过于理论化