Jump Game

题目来源：https://leetcode.com/problems/jump-game/

我的程序（过分复杂了）

class Solution {
public:
    bool canJump(vector<int>& nums) {
        /*ALL IS ABOUT SKIPPING THE ZERO-Prison.mark all the figures before zero to see whether it can skip the zero.WE know that if the start is marked as unable to skip,it fails.however,we should consider the ability of reaching,too.*/
        int length=nums.size();
        if(length==1)
            return true;
        int ability[length];
        for(int i=0;i<length;i++){
            if(nums[i]!=0)
            ability[i]=1;
            else
                ability[i]=0;
        }
        for(int i=length-2;i>=0;i--){
            if(ability[i]==0){
                //cout<<i<<" "<<nums[i]<<endl;
                continue;
            }
                
            else{
                int j=1;
                ability[i]=0;
               //cout<<i<<" "<<nums[i]<<endl;
                if(i+nums[i]>=length-1)
                {
                    //cout<<"!"<<endl;
                    ability[i]=1;
                    continue;
                }
                while(i+j<length&&j<=nums[i]){
                    if(ability[i+j]!=0)
                    {
                        //cout<<"!"<<endl;
                        ability[i]=1;
                        break;
                    }
                    j++;
                }
                        
                }
            //cout<<i<<' '<<ability[i]<<endl;
            }
        for(int i=0;i<length;i++)
            cout<<ability[i]<<endl;
        if(ability[0]==1)
            return true;
        else
            return false;
        }
};

讨论里看到一个很好的代码：https://leetcode.com/problems/jump-game/discuss/318606/6line-C%2B%2B-beat-99-O(N)time-O(1)-space-easy-to-understand

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

这里的k可以理解为起点所可及的范围。在k范围内的点都是可达到的（循环出口改为 k>=(size-1)可能更好理解）

算法的思路如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int size = nums.size();//确定点的个数
        int k = nums[0];//这里的k是原点的原始范围
        for(int i = 0; i <= k; ++i) {//对可及范围内的点一一遍历，实际上这个过程恰好也是随着范围的扩大而不断向右的
            if((i+nums[i]) >= (size-1)) return true;//当范围达到最后一个点时即成功
            else k = max(k, i+nums[i]);//i+nums[i]是当前点所能达到的最大范围，此时其也被并入原点的可及范围中
        }
        return false;//如果上面的扩充过程没有达到终点，则判断不可及
    }
};