45题的时候已经见过这道题了，只不过之前是返回从第 0 个位置能跳到最后一个位置的最小步数，这道题是返回是否能跳过去。
leetCode Solution 中给出的是动态规划的解法，进行了一步一步的优化，但都也比较慢。不过，思路还是值得参考的，上边说的比较详细，这里就不啰嗦了。这里，由于受到 45 题的影响，自己对 45 题的解法改写了一下，从而解决了这个问题。
下边的解法都是基于45题 的想法，大家可以先过去看一下，懂了之后再回到下边来看。
解法一 顺藤摸瓜
45 题的代码。
publicintjump(int[] nums) { intend=0; intmaxPosition=0; intsteps=0; for(inti=0; i<nums.length-1; i++){ //找能跳的最远的maxPosition=Math.max(maxPosition, nums[i] +i); if( i==end){ //遇到边界，就更新边界，并且步数加一end=maxPosition; steps++; } } returnsteps; }
这里的话，我们完全可以把 step 去掉，并且考虑下当前更新的 i 是不是已经超过了边界。
publicbooleancanJump(int[] nums) { intend=0; intmaxPosition=0; for(inti=0; i<nums.length-1; i++){ //当前更新超过了边界，那么意味着出现了 0 ，直接返回 falseif(end<i){ returnfalse; } //找能跳的最远的 maxPosition=Math.max(maxPosition, nums[i] +i); if( i==end){ //遇到边界，就更新边界，并且步数加一end=maxPosition; } } //最远的距离是否到答末尾returnmaxPosition>=nums.length-1; }
时间复杂度：O（n）。
空间复杂度：O（1）。
总
当自己按照 45 题的思路写完的时候，看 Solution 的时候都懵逼了，这道题竟然这么复杂？不过 Solution 把问题抽象成动态规划的思想，以及优化的过程还是非常值得学习的。
