Leetcode: 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.)

Understand the problem:
This question is similar to the last post, but requires minimum number of jumps. 

Solution:
The problem can be solved using recursion as well. It can be categorized the minimal depth of a tree, when we go from root to leaves, we find the minimum depth of the tree. This problem is similar, when we jump from first element to the last, we go through all probabilities and find the minimum number of jumps. 

Code (Java):

public class Solution {
    private int min = Integer.MAX_VALUE;
    public int jump(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        jumpHelper(A, 0, 0);
        
        return min;
    }
    
    private void jumpHelper(int[] A, int start, int depth) {
        if (start >= A.length - 1) {
            if (depth < min) {
                min = depth;
            }
            return;
        }
        int maxJump = A[start] + start;
        for (int i = start + 1; i <= maxJump; i++) {
            jumpHelper(A, i, depth + 1);
        }
    }
}

Discussion:
The time complexity for this solution is exponential. It got the TLE error at OJ. So we must find out another way.

A better solution:
It is natural to think about a DP solution. We can use an array dp[A.length], where dp[i] means the minimum steps from the first element to i. So we only need to check the dp[n - 1]. 

Code (Java):

public class Solution {
    public int jump(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int min = Integer.MAX_VALUE;
        int[] dp = new int[A.length];
        for (int i = 1; i < A.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        
        for (int i = 0; i < A.length; i++) {
            int maxReach = Math.min(A[i] + i, A.length - 1);
            for (int j = i + 1; j <= maxReach; j++) {
                if (dp[j] > dp[i] + 1) {
                    dp[j] = dp[i] + 1;
                }
            }
        }
        
        return dp[A.length - 1];
    }
}

Discussion:
The solution of DP has time complexity of O(n^2).
Summary:
There is another solution using greedy algorithms. We don't discuss it here. 


Update on 10/11/14:

public class Solution {
    public int jump(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        if (A[0] == 0 && A.length > 1) {
            return Integer.MAX_VALUE;
        }
        
        int[] dp = new int[A.length];
        
        // Initialization
        for (int i = 1; i < A.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    dp[i] = dp[j] + 1;
                    break;
                }
            }
        }
        
        return dp[A.length - 1];
    }
}