贪心扣题目分类大纲如下，可以帮助大家在刷题的时候对贪心算法有一个整体的把握。什么是贪心贪心的本质是在每个阶段都选择局部最优，从而达到全局最优。这个有点抽象，举个例子：比如有一叠钞票，你可以拿十张。如果你想达到最大量，你怎么服用？如果每次都指定取最大的，最后的结果就是取最大的。钱。每次取最大的就是局部最优，最后取最大的就是全局最优。再举个例子，如果有一堆箱子，你有一个体积为n的背包，怎么把背包尽可能的装满，如果每次还是选择最大的箱子，那是行不通的。这时候就需要动态规划了。动态规划的问题会在下一个系列中详细讲解。贪心套路（什么时候用greedy）很多同学在做贪心题的时候，想不通这是贪心，想知道有没有什么套路一眼就能看出是贪心的。老实说，贪心算法没有固定的套路。所以唯一的难点就是如何通过局部最优推导出整体最优。那么如何才能看出局部最优能否导致整体最优呢？有什么固定的策略或套路吗？抱歉，没有！自己手动模拟，如果模拟可行，可以试试贪心策略，不行的话可能需要动态规划。有同学问如何验证贪心算法是否可以使用？最好的策略是给出一个反例。如果你想不出反例，那就试试贪心。有的同学可能会认为人工模拟和实例得出的结论不可靠，想要严格的数学证明。数学证明一般有两种方法：数学归纳法和反证法。教科书解释说，贪婪可以是一堆公式。我猜你甚至不想读它们。所以数学证明不在我要说明的范围内。有兴趣的可以自己找资料。在面试中，基本不会要求面试官现场证明贪婪的合理性。编写代码并运行测试用例就足够了，或者证明原因。举个不恰当的例子：我想用1+1=2，但是我想先证明为什么1+1等于2。严谨是严谨，但没必要。这个例子虽然极端，但是可以表达这样一个意思：在做测试或者面试的时候，手动模拟，感觉可以从整体最优中推导出局部最优，如果实在想不出反例，那就试试贪婪。比如刚才说的拿钞票的例子，就是模拟每次拿大的，最后能拿到最多的钱。如果这个需要数学证明，其实不在算法面试的范围之内。你可以看看专业的。数学书！所以这也是为什么很多同学接受了贪心题，却不知道自己用的是贪心算法，因为有时候贪心是常识推导，所以觉得应该做！然后刷题什么时候真的需要数学推导？比如这道题：linkedlist:ringisfound,入口呢？，这道题不需要数学推导，也找不到环的起始位置。如果你想尝试，你不会知道如何尝试，这种题目确实需要一个简单的数学推导。贪心一般求解步骤贪心算法一般分为以下四个步骤：将问题分解为若干个子问题为每个子问题寻找合适的贪心策略求解最优解将局部最优解堆叠为全局最优解solution其实这个子问题有点细化了。真正做题的时候很难分出这么详细的解题步骤。可能是因为贪心题经常和其他方面的知识混在一起。总结本文给出了什么是贪心以及大家关心的贪心算法的固定套路。对不起，贪心没有套路。说白了就是常识推导加反例。最后给出了贪心的一般解题步骤。可以发现这个解题步骤也比较抽象，不像二叉树和回溯算法，给出了这么具体的解题套路和模板。本文没有图片，其实大家可以找一些动漫周边或者搞笑图片来搭配（符合大部分公众号文章的风格），但这不是我的风格，所以本文中的文字说明足够的！
