给定一个非负整数，你最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度，判断你是否能够到达最后一个位置
示例一
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例二
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
简单暴力的递归回溯
从第一个位置开始，根据其可以跳跃的距离进行一个个跳跃，递归搜索，如果递归到0，则返回，继续下一个，直到遍历完所有方案或者找到一个可以到达的方案。
实现：
class Solution {
public:
bool canJump(vector<int>& nums) {
return _canJump(nums, 0);
}
// 递归搜索的方法
bool _canJump(vector<int> nums, int index) {
if(index + 1 >= nums.size()) {
return true;
}
if(nums[index] == 0){
return false;
}
// 可以跳跃的方案
int count = nums[index];
// 穷举每一个跳跃的方案
while(count > 0) {
// 如果其中一个方案可行，就返回true
if( count + index < nums.size() && _canJump(nums, index + count)) {
return true;
}
count--;
}
return false;
}
};
时间复杂度： 2^n，这样的时间复杂度是不太可行的，稍微大一点的数据就会造成超时，不可取
动态规划方法
对于暴力的回溯方法，我们可以发现数组长度是一定的，但是在递归搜索的过程中每个位置是否能走到最后一位，这个结果我们重复计算了很多次，造成了不必要的空间开销。而常规的方法便是引入缓存，新建一个跟数组一样长度的数组，用 -1 、 0 、 1分别表示走不通、未计算、能走通三个状态。然后在递归的初始阶段我们判断这个位置是否被计算过，如果没有被计算过，则继续走下去计算、否则，直接返回计算过的结果
实现：
class Solution {
public:
bool canJump(vector<int>& nums) {
int memo[nums.size()];
for(int i = 0; i < nums.size() - 1; i++) {
memo[i] = 0;
}
memo[nums.size() - 1] = 1;
return _canJump(nums, memo, 0);
}
bool _canJump(vector<int> nums, int memo[], int index) {
if(memo[index] != 0) {
return memo[index] == 1 ? true : false;
}
if(index + 1 >= nums.size()) {
memo[index] = 1;
return true;
}
if(nums[index] == 0){
memo[index] = -1;
return false;
}
int count = nums[index];
while(count > 0) {
if( count + index < nums.size() && _canJump(nums, memo, index + count)) {
memo[index] = 1;
return true;
}
count--;
}
memo[index] = -1;
return false;
}
};
时间复杂度O(n^2)
贪心做法
从后往前找：标记最后一个位置，向前寻找能到达最后一个位置的位置，更新标记为找到的该位置，继续向前找，遍历完毕之后，如果标志位为0，则能达到，如果标志位不为0，则不可以到达
从前往后找：从第一个位置开始，设置一个标志为能到达的最远位置，将当前所在所在位跟能跳跃的位置相加，再跟当前所能跳跃的最远位置相比较从而更新最远位置，一旦当前遍历的位置大于能够跳跃的最远位置，则不能达到，返回false，如果最后能遍历完，则表示能到达，返回true。
贪心从后往前遍历：
class Solution {
public:
bool canJump(vector<int>& nums) {
int lastPos = nums.size() - 1;
for (int i = nums.size() - 1; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos == 0;
}
};
贪心从前往后遍历：
class Solution {
public:
bool canJump(vector<int>& nums) {
int k = 0;
for(int i = 0; i < nums.size(); i++) {
if(i > k) {
return false;
}
k = max(k, i + nums[i]);
}
return true;
}
};
参考：题解
官方题解