他贪心吗？

Question

我正在解决来自 LeetCode.com 的问题：

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false.

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

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 可以解决的问题可以用贪心法解决，但是 这个特定问题 背后的直觉是什么使得用贪心法解决更有意义？

这个SO question在一定程度上突出了这种差异。我知道这可能有点多，但如果可能的话，有人可以在这种情况下回答这个问题吗？我将不胜感激。

谢谢。

编辑：我认为 我感到困惑的原因之一 是输入 [3,3,1,0,4]。根据贪婪范式，当 i=0 时，我们不会为了贪婪地达到输出而跳转大小 3 (A[0]) 吗？但这样做实际上是不正确的。

Answer 1

根据维基百科：

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

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

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

由于在这道题中，我们只关心是否可以到达数组的最后一个索引，所以可以使用贪心算法。贪心算法每一步都会select最优选择（跳得最大），最后检查最大索引是否能到达终点。

也就是说，如果我们需要找出每个索引到达终点的跳转大小或者需要优化到达终点的跳转次数，那么直接使用贪心算法就达不到我们的目的了。

Q2. How is the above solution a greedy algorithm?

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

提供的分析here可能对您有所帮助。

编辑

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

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

请注意，在这个问题中，我们不关心是否应该在 i=0 跳 3 步，尽管我们知道这不会帮助我们到达终点。我们关心的是我们是否可以通过跳跃到达终点或超越终点指标。

他贪心吗？

Is he being greedy?

c++

algorithm

dynamic-programming

greedy