LeetCode 45. Jump Game II（跳格子）_跳格子2

原题网址：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.

For example:
Given array A = [2,3,1,1,4]

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.

方法一：动态规划，用jumps数组记录最小步数。

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

方法二：动态规划，节省空间！

public class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        int from = 0, to = 1;
        for(int step = 1; ; step ++) {
            int nextTo = to;
            for(int i=from; i<to; i++) {
                nextTo = Math.max(nextTo, i + nums[i] + 1);
                if (nextTo >= nums.length) return step;
            }
            from = to;
            to = nextTo;
        }
    }
}