DAY34：贪心算法（一）贪心算法理论基础

课程链接：贪心算法理论基础！_哔哩哔哩_bilibili

什么是贪心算法

贪心算法的本质就是找到每个阶段的局部最优，从而去推导全局最优。

例如一堆不同面额的钞票，取10张，如何取能得到最多的钱？就是每次都取面额最大的钞票。此时面额最大的钞票就是局部最优。全局最优，就是取十次之后拿到了最多的钱。

再举一个例子，比如有一个背包，背包容量是n，最多只能放重量为n的物品。我们有非常多物品，每个物品都有其重量和价值，且每个物品重量与价值不同。

问，装满这个背包，能装的最大价值是多少？（也就是里面物品的最大价值是多少）

这个时候就要考虑如何在装满的同时，还能保证价值最大。背包问题的策略就需要用动态规划来解决。

贪心算法的本质，实际上就是通过局部最优取全局最优。

贪心算法的两个极端

一个是可以直接基于常识性的知识直接判断出来怎么做，思路比较简单；

另一个是完全想不出来，很难想到用贪心去做。

例如取钞票的例子，想要得到最多钞票，每次都取最大值就是常识问题。但是在常识性的问题里也需要方法论，这样遇到难一些的题目才能去思考局部最优这个问题。

如何验证可不可以用贪心算法呢？

刷题或者面试的时候，验证是否可以用贪心算法，最好用的策略就是举反例！手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

面试中基本不会让面试者现场证明贪心的合理性，贪心也不需要做数学推导，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。

真正需要数学推导的情况：类似环形链表

那么刷题的时候什么时候真的需要数学推导呢？

例如这道题目：链表：环找到了，那入口呢？ (opens new window)，这道题不用数学推导一下，就找不出环的起始位置，想试一下就不知道怎么试，这种题目确实需要数学简单推导一下。

贪心的套路

实际上贪心是没有套路的，可以放弃想套路和框架这件事情。

很多比较难的贪心算法题目，属于做过了才能会，没做过没接触不可能做出来的类型。

贪心的一个重要的点，实际上就是要想清楚每个阶段的局部最优解是什么！然后局部最优能不能推出全局最优。

做题/面试的时候，只要想清楚 局部最优 是什么，解释清楚：1.这种局部最优能够推导出全局最优，2.举不出来明显的反例。其实就够了。

数学证明是没有必要的，没有必要证明这道题用反证法or数学归纳法为什么一定要用贪心。因为每道题目的反证法都是不一样的，用反证法无法总结套路。

贪心算法概括一下就是常识性推导，局部最优是什么→能否推出全局最优→举反例的思考过程。