LeetCode 45. Jump Game II

[Woodyiiiiiii]

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.

---

这道题我最先想到的是利用动态规划的思想。dp[i]表示第i个位置的最小步数，状态转移方程是找到i之前的能跳到i的最小步数。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 0;
        for (int i = 1; i < n; ++i) {
            dp[i] = n;
            for (int j = 0; j < i; ++j) {
                if (nums[j] + j >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

这种解法虽然能过所有测试，但超过了时间限制("Time Limit Exceeded")，显然浪费太多运行时间。

这时候我联想到Jump Grame的解法，利用贪婪思想，我们其实仍是只需要关心能跳的最远距离，变量res(也就是所求的最小步数)代表每次最远距离的变化次数，如果当前最远距离max没到末尾位置，我们在能到的距离中寻找能跳的最远距离，更新最远距离索引i，直至能跳到最远位置：

class Solution {
    public int jump(int[] nums) {
        int n = nums.length, res = 0;
        if (n == 1) return 0;
        int i = 0;
        while (i < n) {
            int max = nums[i] + i, mmax = max, index = i;
            ++res;
            if (max >= n - 1) break;
            for (int j = i + 1; j <= max; ++j) {
                if (nums[j] + j > mmax) {
                    index = j;
                    mmax = nums[j] + j;
                }
            }
            i = index;
        }
        return res;
    }
}

总结，我们每次在能跳的步数(所有选择)中找到当前能跳的最远距离(最优选择)，然后直至结束。这也是贪心算法的思想。

---

类似题目：

• 55. Jump Game

参考资料：

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