跳跃游戏 II

一 问题描述

给定长度为 n 的整数数组 nums ，每个元素 nums[i] 代表从索引 i 向前跳跃的最大长度。初始位置为 0 ，返回达到 n-1 的最小跳跃次数。（假定数组一定能跳到 n-1 ）

45.跳跃游戏 II

二 解决方法

1 贪心法

分析1—反向

直接从前往后找到最优的跳跃位置并计算出其所需花费的跳跃次数，并不是很容易（因为无法从判定当前最优位置的下一个位置仍是否最优）。但已知位置 n-1 必可达，不妨反过来试试从后往前找。

假定已经有了第一层的从后往前遍历，那么此时如果第二层循环从前往后遍历，就能找到最优的能跳位置（能从该位置跳跃至当前位置）。因此此时位置越小越优，所以从前往后找到的第一个满足条件的位置即最优位置。

之后，只需要每找到一个最优能跳位置，最小步数加1并跳出该层循环。

代码1

class Solution {
public:
    int jump(vector<int>& nums) {
        int pos = nums.size() - 1;						// 当前元素位置
        int minStep = 0;								// 初始化最小步数为0
        while (pos > 0) {								// 反向遍历数组直到起始位置
            for (int i = 0; i < pos; ++i) {				// 正向遍历找到最优跳跃位置
                if (i + nums[i] >= pos) {				// 找到能达到当前位置的位置
                    pos = i;							// 更新当前位置
                    ++minStep;							// 累加步数
                    break;								// 跳出该层循环
                }
            }
        }
        return minStep;									// 返回最小步数
    }
};

分析2—正向

实际上，计算最小跳跃次数不需要找到最优的跳跃位置，而只要知道最优的可达范围，这可以通过比较现有数组的可达范围而获得。

我们的做法是：从位置 0 开始从左往右遍历，记当前可达最大下标位置为一个临界值（作为完成跳跃一次的标志）。当前位置来到临界位置时，跳跃次数加1，直到遍历至最后位置 n-1 。

又已知数组经过一定次数跳跃必能达到 n-1 位置，也就是说：在倒数第二次跳跃时，其位置必不在 n-1 位置（可以停下来想一想）。因此只需要遍历数组 [0,n-1) ，而不是 [0,n) 。

代码2

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();								// 数组长度
        int minStep = 0, maxPos = 0, end = 0;				// 初始化最小步数，最大下标位置和临界位置为0
        for (int i = 0; i < n - 1; ++i) {					// 遍历数组[0,n-1)
            maxPos = max(maxPos, i + nums[i]);				// 更新当前最大可达范围
            if (i == end) {									// 判断是否达到临界位置
                end = maxPos;								// 更新临界值
                ++minStep;									// 累加最小步数
            }
        }
        return minStep;										// 返回最小步数
    }
};

三 总结

• 当正向遍历不能解决问题的时候，不妨想想反向遍历。

• 有时候信息不需要明确知道。如：本题中只需知道最小步数的每一步的最优范围，而不需知道每一步的具体位置。