044. Jump Game II

这道题依旧遵循 [68. Jump Game](../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;