题目简述：
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
最开始的思路
拿到问题，一看跳跃数组，可以选择位置的那种。选择？哎，这不是二叉树吗，立马就想到使用回溯来做。结果还可以，只是超时了最后一个用例。不过在比赛中应该是可以用的。
下面是回溯算法的代码：
class Solution {
boolean res;
public boolean canJump(int[] nums) {
res = false;
back_trace(nums,0);
return res;
}
void back_trace(int[] nums,int start){
if(start == nums.length - 1){
res = true;
return;
}
int len = nums[start];
if(len == 0){
return;
}
for(int j = 1;j<=len && res == false;j++){
back_trace(nums,start + j);
}
}
}
进阶思路
由于上一步想法超时，检查了一下代码，发现没有可以剪枝的地方，已经是最优了。就觉得不能再使用回溯来做了，回溯既然不行，那么数组的题目大多是dp，那么想着用动态规划来做。
其实也可以用回溯，只是最后和最终思路一样的代码。
这个版本的代码不是很像动态规划，因为没有转移方程，用的是二维数组。其中dp[i][j]代表的是从下标为i的位置是否可以到下标为j的位置。
以下是代码：
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
boolean[] dp = new boolean[len];
dp[0] = true;
for(int i = 0;i < len;i++){
if(dp[i] == true){
int l = nums[i];
for(int j = 1;j <= l && i + j < len && dp[len - 1] == false;j++){
dp[i+j] = true;
}
}
}
return dp[len - 1];
}
}
进一步思路
上面代码超时，那就思考有没有还可以优化的地方。发现使用二维数组有点浪费。不如直接使用一维数组保存已经可以到的下标，并将其置为true。
代码如下：
public boolean canJump1(int[] nums) {
int len = nums.length;
boolean[][] dp = new boolean[len][len];
for(int i = 0;i < len;i++){
for(int j = 1;j <= nums[i] && i + j < len;j++){
dp[i][i+j] = true;
}
}
dp[0][0] = true;
for(int i = 0;i < len;i++){
if(!dp[i][0]){
boolean flag = false;*
for(int j = 0;j < i;j++){
if(dp[j][i]){
flag = true;
break;
}
}
if(flag){
dp[i][0] = true;
}
}
}
return dp[len - 1][0];
}
最终思路
弱化版本的动态规划却也超时，但是上面代码已经是O(n²)了，那么能过的只能是O(n)了。再看上面的代码，发现可以用一个数字来代码已经可以到达的最远距离。而不是使用一个一维数组来保存的结果。
关键在于ans = Math.max(ans,i+nums[i])，通过这个代码可以将已经到达的最远距离用一个数字来表示。
而if(ans >= i)这个判断失败情况下，可以使用不能到达的下标不再进行ans增长。而可以到的下标还可以对ans下标增长。
代码如下：
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
int ans = 0;
for(int i = 0;i < len;i++){
if(ans >= i){
ans = Math.max(ans,i+nums[i]);
}
}
return ans >= len - 1;
}
}