c++ - 他贪心吗？

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;
}

我有两个问题:

1. 为此使用贪心算法背后的直觉是什么？
2. 上面的解怎么算贪心算法？

我认为这可以通过动态规划来解决。我知道 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?

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

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

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 的跳跃，尽管我们知道这不会帮助我们到达终点。我们关心的是我们是否可以通过跳跃到达终点或超越终点指标。