题目
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
解
①暴力递归法，将情况分解为当前元素是0则此路不通，非0的话看元素是几就递归几次，如果出现下标是最后一个元素的话就说明找到一条通路。此解超出时间限制。
class Solution {
private boolean can=false;
public boolean canJump(int[] nums) {
dfs(nums,0);
return can;
}
private void dfs(int[] nums,int index){
//数组，当前下标
if(index==nums.length-1){
can=true;
return;
}
else if(nums[index]==0){
//如果当前的下标元素是0，就返回
return;
}
for(int i=1;i<=nums[index];i++){
if(index+i>=nums.length){
break;
}
dfs(nums,index+i);
}
}
}
②用一个数组遍历所有元素，考虑了各种可能情况，用了很多if-else。简单说，是找到一个元素为0的，然后存储当前下标，往前一个个回溯，查找上一个元素的数据加上元素的下标能否跳过0，如果可以跳过0，则不再向前查找，从跳过的部分开始继续向下。超过99%，50min50s完成
class Solution {
public boolean canJump(int[] nums) {
int index_now = 0;
boolean zero = false;
for (int i = 0; i < nums.length; ) {
if (zero == true) {
//向前回溯想办法跳过index_now的那个0
if (i == -1) {
//如果数组下标变成-1，则表示找不到办法，返回假
return false;
}
if (nums[i] + i > index_now) {
//如果可以跳过存储的0位置
if(nums[i]+i>=nums.length){
//如果跳过后数组已经遍历完成，则返回真
return true;
}
zero = false;
i += nums[i];
} else {
i--;
}
}
else if (nums[i] == 0) {
//如果当前元素是0，则向上寻找跳过该零的方法
index_now = i;//记录当前0的位置,找办法跳过
zero = true;//设置回溯条件，为true时要i--找到可以跳过这个0元素的情况
if(i==nums.length-1)return true;
i--;
} else {
if (i + nums[i] > nums.length - 1) {
//如果往下走会超过数组大小，返回真
return true;
}
i = i + nums[i];
}
}
return false;
}
}
③leetcode解题思路，详细见注释
class Solution {
public boolean canJump(int[] nums) {
//如果一个位置可以到达，那么左侧的所有位置都应该可以到达
int max=0;
for(int i=0;i<nums.length;i++){
//如果当前元素已经超过了能到达的最远距离，就说明不能到达数组最后
if(i>max) return false;
max=Math.max(max,nums[i]+i);//记录当前能到达的最远距离
}
return true;
}
}