Jump Game

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.

最开始想的是一维DP，从后往前，存从这个点能否到终点。

 1 public class Solution {
 2     public boolean canJump(int[] A) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         if(A == null || A.length == 0) return false;
 5         int len = A.length;
 6         boolean[] map = new boolean[len];
 7         map[len - 1] = true;
 8         for(int i = len - 1; i > -1; i --)
 9         {
10             for(int j = 1; j <= A[i]; j ++)
11             {
12                 if(i + j < len && map[i + j] == true)
13                 {
14                     map[i] = true;
15                     break;
16                 }
17             }
18         }
19         return map[0];
20     }
21 }

但是过不了大测试。

一维DP，定义 jump[i]为从index 0 走到第i步时，剩余的最大步数。

那么转移方程可定义为

 jump[i] = max(jump[i-1], A[i-1]) -1, i!=0  
         = 0 , i==0

然后从左往右扫描，当jump[i]<0的时候，意味着不可能走到i步，所以return false; 如果走到最右端，那么return true.

 1 public class Solution {
 2        // DO NOT write int main() function  
 3     public boolean canJump(int[] A) {
 4         // Note: The Solution object is instantiated only once and is reused by each test case.
 5         if(A == null || A.length == 0) return false;
 6         int len = A.length;
 7         int[] map = new int[len];
 8         for(int i = 1; i < len; i ++)
 9         {
10             map[i] = Math.max(map[i - 1], A[i - 1]) - 1;
11             if(map[i] < 0)
12                 return false;
13         }
14         return return map[n-1] >=0;  
15     }
16 }

第二遍：不需要使用数组，只要constant space 即可。

 1 public class Solution {
 2        // DO NOT write int main() function  
 3     public boolean canJump(int[] A) {
 4         // Note: The Solution object is instantiated only once and is reused by each test case.
 5         if(A == null || A.length == 0) return false;
 6         int MaxLengthRemain = 0;
 7         for(int i = 1; i < A.length; i ++){
 8             MaxLengthRemain = Math.max(MaxLengthRemain, A[i - 1]) - 1;
 9             if(MaxLengthRemain < 0) return false;
10         }
11         return true;
12     }
13 }

第三遍：

 1 public class Solution {
 2     public boolean canJump(int[] A) {
 3         if(A == null || A.length == 0) return false;
 4         int step = 0;
 5         for(int i = 1; i < A.length; i ++){
 6             step = Math.max(step, A[i - 1]) - 1;
 7             if(step < 0) return false;
 8         }
 9         return true;
10     }
11 }