55. Jump Game
题意理解：
数组中的每个元素代表最多向后能够跳跃的距离，求解是否能够到达最后的一个元素；
思路
最简单的方法来思考这个问题是问的元素与0的价值是可以避免的吗？这是我构造来回答这个问题的算法，从数组中的第二到最后一个元素，我们将继续递减数组的开始。只有当我们击中一个值为0的元素时，才会停止；在这种情况下，我们评估如果数组的某个地方存在一个元素，该元素的跳值足够大，可以跳过这个0值元素。
97%
public boolean canJump(int[] nums) { if(nums.length <= 1) return true; for(int i = nums.length - 2; i >= 0; i--) { if(nums[i] == 0) { int need = 1; while(need > nums[i]) { need++; i--; if(i < 0) return false; } } } return true; }
45. Jump Game II
这里用一种巧妙并且不太容易理解的贪心算法可以达到O(N)的时间复杂度，只不过在算法中要记录当前一跳所能到达的最远距离、上一跳所能到达的最远距离，和当前所使用跳数就可以了。另外需要注意的一点是：题意要求不一定非得跳到last index，越过去也算，这点需要特别强调。
public int jump(int[] nums) { int ret = 0;//当前跳数 int last = 0;//上一跳可达最远距离 int cur = 0;//当前一跳可达最远距 for (int i = 0; i < nums.length; ++i) { //无法向前继跳直接返回 if(i>cur){ //有可能无论怎么跳，都不能到达终点或者越过终点，比如[3,2,1,0,4]。 return -1; } //需要进行下次跳跃，则更新last和当执行的跳数ret if (i > last) { last = cur; ++ret; } //记录当前可达的最远点 cur = Math.max(cur, i+nums[i]); } return ret; }
接下来，第一元素告诉cur，可以向前走2步。于是：
下一循环中，i指向index 1（图中的元素3），发现i大于last能到的范围，于是进行跳跃。步数ret加1.同时要更新cur。因为发现了新的最远距离。
接下来，i继续前进，发现i=last，无需更新last和步数ret。更新cur。
i继续前进，发现i>last，更新last和步数。cur已经最大了。
最后，i到最后一个元素。遍历完成，返回ret。
