给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。=
判断你是否能够到达最后一个位置。

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1

数学题的思路，主要有两点。

• 如果数组全部是正数，则肯定能跳过去。
• 从右向左遍历，如果当前a[i]为0，则看是否能跳过此0(最后一个0除外)，也就是说，在其左边(j<i)，至少有一个点满足可以跳过此 0，即存在a[j]>(i-j),否则跳不过去此0，自然无法达到最右。

code：

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;
    }

思路2

则可以使用动态规划的思路。

• 子问题
  这里的子问题可能稍微难找点，我也是看了别人的视频教程，但是这种思维方式感觉很棒。
  加入我们用d[i]表示能否到达i点，如果可以，则为true，否则为false。
  那么d[]如何通过前面的状态推算出来呢?
  我们注意到：如果可以到达j点(j<i),即d[j]=true,且d[j]>=i-j,则表明可以到达i点，而且这样的j只要存在一个就好了。
• 转移方程。
  转移方程不是很好写：大概就是翻译了一下子问题分析里面的规律。
  
• 边界值。
  边界值就简单了，即0借点肯定是可以到达的。即d[0]=true
• 动态规划求解

code:

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];
    }