45. Jump Game II

45. Jump Game II

Given an array of non-negative integers nums, 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.

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

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 1000

• 0 <= nums[i] <= 105

My Solutions:

方法1：用一个steps数组储存到达这个位置的时候，所需要的最小步数。结果返回steps中最后一个位置的数。

方法2：在每一个位置，用max记录在此位置时，可以向前走到的最远位置。如果当前位置的index和之前lastJumpMax相同（之前跳到的位置），说明此时必须要跳，所以steps++，lastJumpMax更新为max。结果返回steps。

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        // 方法1
//         int[] steps = new int[len];
        
//         steps[0] = 0;
//         for (int i = 1; i < len; i++) steps[i] = Integer.MAX_VALUE;
        
//         for (int i = 1; i < len; i++) {
//             for (int j = 0; j < i; j++) {
//                 if (steps[j] != Integer.MAX_VALUE && j + nums[j] >= i) {
//                     steps[i] = Math.min(steps[i], steps[j] + 1);
//                 }
//             }
//         }
//         return steps[len - 1];
        
        // 方法2
        int lastJumpMax = 0, steps = 0, max = 0;
        for (int i = 0; i < len - 1; i++) {
            max = Math.max(max, i + nums[i]);
            if (i == lastJumpMax) {
                steps++;
                lastJumpMax = max;
            }
        }
        return steps;
        
    }
}