这道题依旧遵循 68. Jump Game 的思路，当时我并未理解所用方法应该属于哪种经典算法的范畴。

今天看来应该属于贪心法的范畴。每次记录最远距离，即为局部最优解。确能推得整体最优解（是否能达到末尾）。

在这道题里，可能要对上次的代码做出一点修改：

  1. 因为只需最小的 jump，那么肯定要记录 step 数，故增加变量 step.
  2. 与上一道题一样，每一步都需要统计 max，但这个 max 并不一定为我所用，故改为 tmpMax
  3. 增加新的 max，用来记录最小步数的 max 步数，用以验证是否能够达到末尾。

然后说明一下，step 的策略肯定是越少越好，也就是能不加就不加。所以我们用 max 为限，当迭代的 i 到达了 max 时，那是不得不加了。 此时能拿到的最远距离，如果达到了末尾，表示已经用了最少的 step, 反之，则是上一次记录的 step 为最少，或也可能永远到不了末尾。

int step = 0, max = 0;
for (int i=0, tmpMax = 0; i<max && i<n-1; ++i) {
    tmpMax = std::max(tmpMax, A[i]+i);
    if (i == max) { // 当 i 到达上次记录的最远位置
        max = tmpMax;   // 更新 max 记录
        ++step; // 这算一步
    }
}
return max >= (n-1) ? step : -1;
#include <algorithm>

class Solution {
public:
    int jump(int A[], int n) {
        int step = 0, max = 0;
        for (int i=0, tmpMax=0; i<=max && i<n-1; ++i) {
            tmpMax = std::max(tmpMax, A[i]+i);
            if (i == max) { max = tmpMax; ++step; }
        }
        return max >= (n-1) ? step : -1;
    }
};

LeetCode Direct Link