为什么 Greedy 可能感觉不直观（以及我如何理解它）

Source: Dev.to

抱歉，我无法直接访问外部链接获取文章内容。请您把需要翻译的文本粘贴在这里，我将为您翻译成简体中文，并保留原始的格式、Markdown 语法以及技术术语。

动机

有人在 Discord 上询问如何在并不明显的问题中识别贪心解法。他们特别提到了两个问题：Jump Game 和 Container With Most Water，并表示对这些问题使用贪心感觉不直观。

老实说，我第一次尝试这些问题时，根本无法独立完整地解出来。即使我有意识地练习已知是贪心的题目，我仍然会产生同样的疑惑。贪心对我来说也不自然。因此，当我看到有人在 Discord 上提出这个问题时，我决定更深入地思考一下，看看会有什么发现。

我主要关注这两个问题。对于每个问题，我先凭直觉走了一遍，得到它所指引的解法。随后，我尝试追溯这种直觉的来源，将其与贪心解法进行对比，弄清楚为什么一种方法比另一种更自然。

盛最多水的容器

给定一个高度数组，其中每个索引代表一条垂直线。目标是选择两条线，使它们形成的容器能够容纳最大量的水。

在这个问题中，我的直觉竟然直接指向了预期的贪心解法。一个可能的原因是，我看不出对最初想到的暴力破解方法进行任何有意义的优化。于是，我没有坚持使用暴力破解并尝试改进，而是以不同的方式来思考这个问题。

我首先明确了目标：最大化面积。理想情况下，这意味着既要有最大的宽度，又要有最大的高度，但实际上这并不总是可能的。于是，我把问题重新定义为在宽度和高度之间寻找最佳的折中。我从最大的可能宽度开始，然后尝试在可能的情况下提升高度，即使这意味着要牺牲一些宽度，只要高度的提升能够弥补宽度的损失即可。

在写这些文字时，我意识到贪心方法也可以被视为对暴力破解的优化。在暴力破解中，我们会考虑每一种可能的容器并比较它们的面积。而在贪心解法中，我们并不会构造每一个容器，而是有意识地丢弃那些我们已经知道不可能是最优的容器，因为当前的贪心选择已经支配了它们。这正是该方法既高效又安全的原因。

跳跃游戏

给定一个数组，其中每个值表示从该索引向前最多可以跳多少步。从索引 0 开始，问题就是看能否到达最后一个索引。

对于跳跃游戏，一开始我并没有想到使用贪心算法。我想这是因为我把问题严格地框定为“如何到达目标？”——这自然会引出一种动态规划（DP）式的解法。然而，当我后来看到更高效的贪心解法时，我意识到换一种思考方式会让问题显得不那么直观。

如果把问题视为一个距离问题——即索引 0 是离终点最远的点——目标就变成从起点尽可能向前推进，并检查这种可达范围是否最终覆盖了最后一个索引。从这个角度看，贪心解法只是一步一步地扩展可达范围，而不是直接去瞄准目标。

结论

我认为贪心算法让我感到害怕的部分原因是，我很难证明它的正确性，甚至连自己也难以说服。它常常让我觉得自己像是盲目一搏、寄希望于它能奏效，而不是进行“真正的工作”，即恰当地推理。这大概是因为我还没有超出非正式定义去理解贪心算法。

我的收获是，提升对为何贪心选择是安全的推理能力会让这些解法变得更自然。与此同时，以不同方式重新构造问题并反思直觉驱动的解法实际是如何工作的，似乎是随着时间积累贪心直觉的好方法。