55. 跳跃游戏

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

bool canJump(vector<int>& nums) {
        int sz=nums.size();
        if (sz<=1) {
            return true;   // 特殊情况
        }
        if (nums[0]==0) {  // 如果第一个就是0，那么不可能到达 
            return false;
        }
        
        // 这里的思路是：如果找到0，那么看前面是不是都满足能跳过这个0，如果从任何一个点都跳不过这个0，
        // 那么则到达不了最后,这个0是最后一个0除外，所以下面的循环是从sz-2开始 
        for (int i=sz-2; i>0;i--) {  
            int cnt=0;
            if(nums[i] == 0) {
               for (int j=0; j<i; j++) {
                   if(nums[j]>i-j) {
                      cnt++; 
                      break;  //只要能找到一个，就可以退出了。
                   }
               }
               if(cnt==0) {
                   return false;
               }
            }
        }
        return true;
    }

bool canJump(vector<int>& nums) {
        int sz=nums.size();
        // 特殊情况
        if(sz <=1) {
            return true;
        }
        if(nums[0]==0) {
            return false;
        }
        
        vector<int> dp(sz,0);
        dp[0]=1;
        for(int i=1; i<sz;i++) {
            for (int j=0;j<i;j++) {
                if(dp[j]==1 && nums[j]>=(i-j)) {
                    dp[i]=1;
                    break;
                } //如果当前的节点可以到达，并且可以越过节点i，则说明可以达到节点i，则节点i可以置位true，然后跳出当前循环
            }
        }
        return dp[sz-1];
    }