Jump Game I && 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. 

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

First thought, 1D DP, the current point can be reached as long as any of the previous points has the maximum step greater than the distance from that point to this point, i.e., can[i] = (can[j] & (j + A[j] >= i).

public boolean canJump(int[] A) {
        boolean[] can = new boolean[A.length];
        can[0] = true;
        
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (can[j] && j + A[j] >= i) {
                    can[i] = true;
                    break;
                }
            }
        }
        
        return can[A.length - 1];
    }

Of course, didn't pass the time limit!

Second thought, greedy approach, and with a similar idea. Use a number to track the farthest point it can reached. At point i, the farthest point it can reach is A[i] + i. So keep tracking the farthest point it can reach and return if it is greater than A.length - 1.

public class JumpGame {
    public boolean canJump(int[] A) {
        int farthest = 0;
        for (int i = 0; i <= farthest && i < A.length; i++) {
            farthest = (A[i] + i > farthest) ? (A[i] + i) : farthest;
            if (farthest >= A.length - 1)
                return true;
        }
        return false;
    }
}

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

Still greedy approach. At each position "farthest", find the maximum position, "maxPos" it can reach, jump to that, and get the next maximum position it can reach. When the maximum position reaches the end of the array, break the loop and return number of jumps needed.

Update: 2015 - 01 - 16
An example that may be helpful to understand:
2   1   3   2   1
index = 0, maxPos = 2;
farthest = 2, numSteps = 1;
index = 0, maxPos = 2;
index = 1, maxPos = 2;
index = 2, maxPos = 5;
farthest = 5, numSteps = 2;
break, return 2

public class JumpGame {
    public int jump(int[] A) {
        if (A == null)
            throw new NullPointerException("Null array!");
        if (A.length <= 1)
            return 0;
        int farthest = 0;
        int maxPos = 0;
        int index = 0;
        int numSteps = 0;
        while (index < A.length) {
            if (farthest >= A.length - 1)
                break;
            while (index <= farthest) {
                maxPos = Math.max(maxPos, A[index] + index);
                index++;
            }
            farthest = maxPos;
            numSteps++;
        }
        return numSteps;
    }
}