概要
给定一个非负整数的数组，从起始位置开始跳跃，每个数字代表能够跳跃的最大距离，判断是否能够跳跃到末尾位置。
贪心算法
回顾贪心算法的两个要素：
- 在当前状态能够找到一个安全的行动；
- 问题具有最优子结构。
很容易看出，本题具有最优子结构。每次将跳跃到的位置之前的元素删除，即可得到与原问题性质一致、但规模较小的子问题——在剩下的较小的数组中判断是否能从起始位置跳到末尾位置。因此尝试使用贪心算法解决本问题。
现在应当考虑如何进行安全的一步操作，以制定贪心策略，进一步来说，问题可以理解成视解为下标的一个序列，能否跳跃到一个在这个序列当中的一个位置。
错误的贪心策略可能有：
- 从起始位置出发，每次跳跃到最远的位置。
- 从起始位置出发，每次跳跃到数字最大的位置。
- 从起始位置出发，每次跳跃到能够到达的位置的值之和最大的位置。
- …
要注意的是，数组的起始位置不一定在解当中，因此从起始位置起步是不合适的，从末尾位置开始才是正解。
正确的贪心策略是：
从末尾位置出发向前找，每次找一个能够跳到末尾位置的位置，并从这个新位置出发重复寻找操作，直到回到了起始位置（成功）或无法再往前跳跃（失败）。
这样确保了每次都能找到一个在解中的位置，并且当多个位置满足要求时，由于它们都能到达同一个位置，这些位置也是相互能回溯到的。
如此这般，本题能够在遍历一遍数组（$O(n)$)的情况下返回结果。