45.Jump Game II

Tags: Hard Greedy Array

Links: https://leetcode.com/problems/jump-game-ii/

---

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.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

---

class Solution {
public:
    int jump(vector<int>& nums) {
        int cnt = 0, n = nums.size();
        if (n == 1) return cnt; //特殊情况，数组只有一个元素

        int pos = 0;
        int curLength = nums[pos] + pos; //代表当前点所能到达的最远距离
        while (curLength < n - 1) {
            int nextPos = pos;
            int tmpMax = curLength;
            for (int i = pos + 1; i < n && i <= curLength; ++i) {
                if (i + nums[i] > tmpMax) {
                    tmpMax = i + nums[i];
                    nextPos = i;
                }
            }
            ++cnt;
            curLength = tmpMax;
            pos = nextPos;
        }

        return (cnt + 1);
    }
};

上面的方法是利用贪心的方法，还可以采用动态规划的思想：

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        //vector<int> pre(n); //用来记录转移
        f[0] = 0;
        int last = 0;
        for (int i = 1; i < n; i++) { // 依次求f[i]的值。
            while (i > last + nums[last]) // 根据i来更新last。
                last++;
            f[i] = f[last] + 1; // 根据f[last]更新f[i]。
            //pre[i] = last; //记录路径
        }
        return f[n - 1];
    }
};

(动态规划，贪心优化) O(n)O(n)

• 首先定义两个指针last和i，数组f[i]表示到达i所需要的最少步数。
• 定义last为第一次到达i时上一步的位置，last从0开始。
• 根据贪心得知，令f[i]=f[last]+1后，f[i]就会是最优值。
• 故可以根据i来让last向后移动，找到最早的可以一步到达i的位置，然后根据f[last]更新f[i]。

这道题目其实还可以进一步思考，如果需要输出路径呢？

只需要一个数组pre来记录是从哪个转移归来的，然后递归输出即可。