题解 | #跳跃游戏(一)#

核心思路：

算出来每个位置的最远距离即可。最远距离达到尾部了就算true

举个例子：[2,1,3,2,0,0,100]

• 当下标为0，我们可以得到最远距离到下标为2的位置
• 当下标为1，我们可以得到最远距离到下标为2的位置
• 当下标为2，我们可以得到最远距离到下标为5的位置
• 当下标为3，我们可以得到最远距离到下标为5的位置
• 当下标为4，我们可以得到最远距离到下标为5的位置
• 当下标为5，我们可以得到最远距离到下标为5的位置

到最后我们也没得到一个最远距离 >= 6的位置，所以返回false

并且过程中我们还要考虑到一个断档问题：即，别说跳到终点，中间就有可能有一大堆零，跳不过去了。

所以我们的循环要一直控制在目前能跳到的最远距离范围。

c++实现

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // write code here
        if(nums.size() == 1) return true;
        vector<int> dp(nums.size()-1);  //dp用来记录每一步的值
        dp[0] = nums[0];
        int m=nums[0];  //m用来存储当前最大值
        for(int i=1; i<=m && i<nums.size()-1; i++){  //注意判断条件，除了不能超过nums.size，还要小于最大距离
            dp[i] = max(i+nums[i], dp[i-1]);  //当前下标+能迈的步数 与 之前的最大值 相比较
            if(dp[i] > m) m = dp[i];     //留存最大值
            if(m >= nums.size()-1) break;  //如果已经能达到终点，直接break即可
        }
        if(m >= nums.size()-1){
            return true;
        }else{
            return false;
        }
    }
};

但是写完了以后，想了想，dp这个容器其实没有必要存在，因为dp的最后一个永远是最大值，那我们其实只需要存一个最大值就够了。

以下是优化后的代码：

c++优化版

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // write code here
        if(nums.size() == 1) return true;
        int temp = nums[0];
        for(int i=0; i<=temp; i++){
            temp = max(i+nums[i], temp);
            if(temp >= nums.size()-1) return true;
        }
        return false;
    }
};