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.
开始的想法比较复杂，O(N^2)的复杂度，大数据测试超时了，然后改进了一下，设一个标志位表示第一个不可达的下标，最后判断最后一个元素是否可达，复杂度为O(N)，代码如下
1 public boolean canJump(int[] A) { 2 if (A.length <= 1) { 3 return true; 4 } 5 boolean p[] = new boolean[A.length]; 6 p[0] = true; 7 int pos = 1; 8 for (int i = 0; i < A.length; i++) { 9 if (p[i]) { 10 for (int j = pos - i; j <= A[i] && i + j < A.length; j++) { 11 p[i + j] = true; 12 } 13 } 14 if (p[p.length - 1]) { 15 return true; 16 } 17 } 18 return false; 19 }
看了下网上的，这个写的比较简单，复杂度也是O(N)，思路就是找到第一个不可达的下标，判断是不是大于最后一个元素的下标，代码如下
1 public boolean canJump(int[] A) { 2 int max = 0; 3 for (int i = 0; i < A.length && i <= max; i++) { 4 max = A[i] + i > max ? A[i] + i : max; 5 } 6 return max >= A.length - 1; 7 }
贪心策略，局部最优等于全局最优？
差距就是本来5行代码能搞定的我却要写15行。。。0.0
原文：http://www.cnblogs.com/apoptoxin/p/3737195.html