Jump Game II

For this quesiton, Greedy should be an efficient method. However, I took DP at first, which got TLE, even though I tried some improvements. I believe my code can get correct result, but time limit is always exceeded. Since I had some things to deal with, to save time, I checked out solution posted by Code_Ganker, where I got his greedy idea. Excellent! Hope next time I can work this question out by myself.

// My code, get TLE

public class Solution {
    public int jump(int[] A) {
        int minStep = 0;
        int []B = new int[A.length];
        Arrays.fill(B,-1);
        // recursively
        minStep = minJump(A,0,B); //start from 0 ,then recursion.
        return minStep;
    }
   
    public int minJump(int[] A, int idx, int[] B ){
        if(idx >= A.length - 1) {
            return 0;
        }
        if(B[idx] != -1) return B[idx];

        int step = A[idx];
        int minJumpNum = Integer.MAX_VALUE;
        for(int i = step; i >= 1; i --){
            // if(idx + i < A.length)  
            minJumpNum = Math.min(minJumpNum, 1 + minJump(A, idx + i, B));
        }
       
        B[idx] = minJumpNum;
        return minJumpNum;
    }
   
}

// Code_Ganker's code
public class Solution {
public int jump(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int lastReach = 0;
    int reach = 0;
    int step = 0;
    for(int i=0;i<=reach&&i<A.length;i++)
    {
        if(i>lastReach)
        {
            step++;
            lastReach = reach;
        }
        reach = Math.max(reach,A[i]+i);
    }
    if(reach<A.length-1)
        return 0;
    return step;
}
}

For explanation, please check this url out:

http://blog.csdn.net/linhuanmars/article/details/21356187