给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。=
判断你是否能够到达最后一个位置。
示例 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];
}
