Jump Game

Jump GameMar 25 '12

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.

Solution 1: 
You can treat it as a dynamic programming question. If you want to know whether you can jump to the end from the current node, you should know the situations in the positions that the current nodes can go through one jump. Then do it backwards.

01 public boolean canJump(int[] A) {

02     int len=A.length;

03     boolean [] results=new boolean [len];

04     results[len-1]=true;

05     for(int i=len-2;i>=0;i--)

06     {

07         int value=A[i];

08         if(value+i>=len-1)

09         {

10             results[i]=true;

11         }

12         else

13         {

14             for(int j=1;j<=value;j++)

15             {

16                 if(results[i+j]==true)

17                 {

18                     results[i]=true;

19                     break;

20                 }

21             }

22           

23         }

24       

25     }

26     return results[0];

27 }

Solution 2:
Instead using DP, we can use greedy. Calculate the farthest position it can jumps to. If the farthest position is greater than or equal to the last index of the array, return true, else return false.

01 public boolean canJump(int[] A) {
02     int farthest=A[0];
03     int i=1;
04     while(i<=farthest && i<A.length)
05     {
06         if(A[i]+i>farthest)
07         {
08             farthest=A[i]+i;
09         }
10         i++;
11     }
12     if(farthest>=A.length-1)
13         return true;
14     else
15         return false;
16 }