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.

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.

解法1：Greedy O(N) Time O(1) Space

这题可以作为复习Greedy Algorithm的一个很好的范例。最核心的思想和Jump Game一样，用一个变量维护上一步可以走到的最远距离。如果当前的距离比他远，则说明需要额外的一步。同时维护一个下一步可以走到的最远距离，便是在当前的最远距离和i + nums[i]中取最大值即可。

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int jump(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // Greedy
        int cur = 0;
        int last = 0;
        int step = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > last) {
                last = cur;
                step++;
                if (last >= nums.length) {
                    return step;
                }
            }
            cur = Math.max(cur, i + nums[i]);
        }
        return step;
    }
}

解法2：Greedy O(N) Time O(N) Space, DP thinking

用一个dp数组来存储每一个点所需要的最少步数。
然后从0开始扫描，找出当前点所能到的最远距离。然后从下一位置开始扫描，对于每一个可以到达的点都更新最少的步数，也就是dp[j] = dp[i] + 1。到此，j位置上的结果已经找出，不会再有比他步数更少的解了。
最后返回dp[n-1]即可。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int jump(int[] nums) {
        int[] dp = new int[nums.length];
        // dp pointer
        int j=1;
        for (int i=0; i<nums.length; i++) {
            int loc= nums[i] + i;
            while (j<=loc && j<nums.length) {
                dp[j] = dp[i] + 1;
                j++;
            }
        }
        return dp[dp.length-1];
    }
}