[刷题防痴呆] 0045 - 跳跃游戏 II (Jump Gam

题目地址

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

题目描述

45. 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.

思路

1. 动态规划, O(N2), 会超时. 当前层能不能跳到取决于, 前面的每层中, 有可以跳到当前层, 并且前面层高与前面层可跳到的层数相加大于当前层高. 这题在1的基础上, 把boolean变成存min.
2. 贪心, O(N). 如果当前位置是当前能到的最大位置, jump + 1. 更新curMax为能到的最大层, 不停重复以上步骤.

关键点

• 动态规划的解法.
• steps[0] = 0. 其他为Integer.MAX_VALUE.
• 如果steps[j] != Integer.MAX_VALUE && j + A[j] >= i, steps[i] = Math.min(steps[i], steps[j] + 1).
• 贪心的解法.
• for loop不能到最后一个index,否则当 curMax == i, jump会加1.

代码

• 语言支持：Java

// 方法1, dynamic programming
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] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (dp[j] != Integer.MAX_VALUE && j + nums[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

// 方法2, Greedy
class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        
        int step = 0;
        int curMax = 0;
        int farest = 0;
        
        for (int i = 0; i < nums.length - 1; i++) {
            farest = Math.max(farest, i + nums[i]);
            
            if (i == curMax) {
                step++;
                curMax = farest;
            }
        }
        
        return step;
    }
}