Leetcode : jumpGame
题目
题目很简单，给一个非负整数的数组，每一个数组中的元素代表在这个起点，可以最大往前跳跃的格子数。
在这里引用一下leetcode上举的例子：
Example_1
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example_2
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
解决思路
感觉算是一个入门级别的动态规划题目。
用动态规划是最简单，也是耗时最短的，时间复杂度为O(N)
还有其他解法就不列举了，有兴趣可以在本文末尾的引用链接看看。
我的具体思路是，保存一个 int 类型的变量 maxJump，代表在 i 这个格子之前，可以跳到 i 格子的最大步数。那么可以知道，如果 maxJump 大于0，那么是可以跳到 i 这个格子的。
那本题的解就是 在指向最后一个格子 end 的时候 maxJump 必须大于0，才能够跳到最后一个格子。
这个前提是已经能跳到 end-1 个格子，那么问题就变成了，是否可以跳到 end-1 的格子。
可以归纳为 can[i] = can[i-1] && (maxJump>0);
具体写法，初始的maxJump=nums[0]; 然后从 index=1 开始迭代。每次往前推一个index，maxJump需要减一。然后和当前格子的值比较，更新maxJump为较大的值。
代码如下：
public boolean canJump(int[] nums) {
int maxJump = nums[0];
for(int i=1; i<nums.length; i++){
if(maxJump-- <= 0){
return false;
}
maxJump = maxJump > nums[i] ? maxJump : nums[i];
}
return true;
}
执行时间超过Java提交91.89%。
这里要注意的一点是，如果比较最大的那个改成 Math.max()函数，时间就降到了 66.7%。里面实现是一样的，应该是Math类加载的耗时。（对于执行时间短的算法，感觉这是一个优化的思路）
