LeetCode - Jump Game II
Problem description
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:
1
2
3
4
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.
Analysis
The first thought is to use the Brute Force method, we use an DP array to store the steps. dp[i] means steps to reach position i.
Here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class JumpGameII {
public int jump(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j <= Math.min(nums.length - 1, i + nums[i]); j++) {
dp[j] = Math.min(dp[j], dp[i] + 1);
}
}
return dp[nums.length - 1];
}
}
Another idea is that use maxStep to indicate max position this jump can reach and maxPos to indicate max position in next jump.
Here’s the code:
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
class Solution {
public int jump(int[] nums) {
int n = nums.length;
if (n < 2) return 0;
// max position one could reach
// starting from index <= i
int maxPos = nums[0];
// max number of steps one could do
// inside this jump
int maxSteps = nums[0];
int jumps = 1;
for (int i = 1; i < n; ++i) {
// if to reach this point
// one needs one more jump
if (maxSteps < i) {
++jumps;
maxSteps = maxPos;
}
maxPos = Math.max(maxPos, nums[i] + i);
}
return jumps;
}
}
What to improve
- idea is similar but use extra memory and time.