代码随想录—贪心 | Aryue的个人博客

type

status

date

slug

summary

🤔 综述

对于贪心算法问题，我们不能仅从容易到困难的方式进行。否则，我们可能会在不知不觉中在简单的问题上使用贪心策略。下面我会解释具体的原因。

贪心算法的本质是在每个阶段选择局部最优解，以达到全局最优。比如，分发饼干时，从胃口值最大的孩子开始遍历，如果有饼干可以满足，就将其分配给该孩子。遍历完一遍后，就能得出最大数量的分配方案。

在此过程中，局部最优指的是要尽量不浪费大饼干，将大饼干尽量分配给胃口值大的孩子。如果局部都能满足这个条件，全局自然就是最节俭的。

这种类型的问题并没有固定的解决方法，因为每种类型的问题都有不同的局部最优解决方案。

这部分不需要进行数学证明，虽然整体上类似于数学归纳法，但是如果要进行严格的数据证明仍然很困难，那是数学专业的事情。

简单题目，就是凭感觉和常识，比如以下题目：

中等题目可能就不能仅凭常识了，有一定难度，需要熟悉套路。

比如区间问题，就是比较困难的题目了，一般来说需要进行大量的分析，可能还需要排序辅助。

还有一些困难题目，比如最大子序列、加油站、监视二叉树等，需要过一段时间回来重新温习。

由于贪心部分没有固定的套路，因此本文的篇幅不长。实际上，贪心部分的题目也不难，只要按部就班地熟悉题目的套路即可。

致谢：

💡

Written by Aryue,editted by Notion AI.