他贪婪吗？

Question

我正在从LeetCode.com解决一个问题:

给定一个非负整数数组,您最初定位在数组的第一个索引处.数组中的每个元素表示该位置的最大跳转长度.确定您是否能够到达最后一个索引.例如:A = [2,3,1,1,4],返回true.A = [3,2,1,0,4],返回false.

投票最多的解决方案之一(这里)说以下是使用贪婪的方法:

bool canJump(int A[], int n) {
    int last=n-1,i,j;
    for(i=n-2;i>=0;i--){
        if(i+A[i]>=last)last=i;
    }
    return last<=0;
}

我有两个问题:

我认为动态编程可以解决这个问题.我理解DP可以解决的问题可以通过贪婪的方法来解决,但是这个特殊的方法背后的直觉是什么使得通过贪婪的方法解决更有意义？

这个问题在某种程度上凸显了这种差异.我理解这可能会更多,但如果可能的话,有人可以在这个背景下回答这个问题吗？我非常感谢.

谢谢.

编辑:我认为我混淆的原因之一是输入[3,3,1,0,4].根据贪婪的范式,i=0我们何时不会跳过大小3(A[0])来贪婪地达到输出？但这样做实际上是不正确的.

Answer 1

根据维基百科：

贪心算法是一种算法范式，遵循问题解决启发式，在每个阶段做出局部最优选择，以期找到全局最优值。

在这里，我想提请您注意关键词，每个阶段的局部最优选择，这使得算法范式变得贪婪。

Q1. What is the intuition behind using a greedy algorithm for this?

由于在这个问题中，我们只关心是否有可能到达数组的最后一个索引，因此我们可以使用贪心算法。贪心算法会在每一步中选择最优选择（采取最大跳跃），并在最后检查最大索引是否可以到达末尾。

比如说，如果我们需要找出每个索引处到达末尾的跳转大小或者需要优化到达末尾的跳转次数，那么直接使用贪心算法将无法达到我们的目的。

Q2. How is the above solution a greedy algorithm?

if上面代码中的条件 -使if(i+A[i]>=last)last=i;算法变得贪婪，因为如果可能的话我们会采取最大跳跃（i+A[i]>=last）。

这里提供的分析可能会对您有所帮助。

编辑

让我们谈谈您提到的输入 - [3,3,1,0,4]。

当时i=0，算法检查我们可以到达的最大索引是多少i=0。
然后我们将移动到下一个索引并检查我们可以到达的最大索引是多少i=1。由于我们移动到i=1，所以可以保证我们可以从索引 0 到达索引 1（与跳转大小无关）。

请注意，在这个问题中，我们并不关心是否应该在 at 进行大小为 3 的跳跃，i=0尽管我们知道这不会帮助我们到达终点。我们关心的是我们能否通过跳跃到达终点或者超越终点索引。