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

这一题被我和前面一题“几步可以从头跳到尾”思路混淆了，道理上说两个题目表达的意思是一样的，但是不知怎么滴我都转不出来了，按照前面的思路写出来的程序如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool canJump(vector<int>& nums) {
        // write code here
        int n=nums.size();
        vector<bool> dp(n,false);
        dp[0]=true;
        int j=0;
        for(int i=1;i<n;i++)
        {
            while(j<n && j+nums[j]<i) j++;
            if(j==n-1)
                break;
            dp[i]=true;
        }
        return dp[n-1];
    }
};

重点在于最后一个测试用例(1,1,1,1,1,1,1~~~~~~~)

后来看了题解，一种很简单清新的思路和程序：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool canJump(vector<int>& nums) {
        // write code here 主要就围着nums[i]+i转 能走就走，不能走就停滞
        int x=nums[0];
        for(int i=0;i<=x;++i){
            if(nums[i]+i>=nums.size()-1) return true;
            x=max(x,nums[i]+i);
        }
        return false;
    }
};