Problem Description

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

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

Solution

First thought is to use DP. For this, we have to disassemble it to easier sub-problems and build the iterations. For example, if we know the minimum number of jumps at all positions from i to len-1, how to compute the answer at i-1? This is then a quite straightforward problem. So we just need to solve those sub-problems iteratively until we reach 0.

Another idea is to view the problem from a different view of point: how far we can reach given a fixed number of jumps? Suppose we are at i, and if the furtherest point from i can not reach the end, we need at least two more jumps, now the problem is how to find next the landing point? Maximize your reach point with these two jumps. So we simply scan all possible points from i and compute the max point to determine the next landing point.

Java Code

DP

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        if(len == 1) return 0;
        int[] dp = new int[len];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[len-1] = 0;
        for( int i=len-2; i>=0; i--){
            for( int j=1; j<=nums[i]; j++ ){
                if( i+j >= len-1) dp[i] = 1;
                else if(dp[i+j] < Integer.MAX_VALUE) dp[i] = Math.min( dp[i], dp[i+j]+1 );
            }
        }
        return dp[0];
    }
}

Greedy BFS

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        if(len == 1) return 0;
        int max_id = nums[0], cnt = 1, prev_max=0, next_max;
        while( max_id < len-1 ){
            next_max = max_id;
            for( int i=max_id; i > prev_max; i--) next_max = Math.max(next_max, i + nums[i]);
            prev_max = max_id;
            max_id = next_max;
            cnt ++;
        }
        return cnt;
    }
}