LC55、跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

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

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

法1：递归，但是超时

 1 class Solution {
 2 public:
 3     bool available(vector<int>&  nums,int index){
 4         if(nums[index]+index>=nums.size()-1)
 5             return true;
 6         else{
 7             int a = nums[index];
 8             while(a && (a+index)<nums.size()){
 9                 if(available(nums,a+index))
10                     return true;
11                 a--;
12             }
13             return false;
14         }
15     }
16     bool canJump(vector<int>& nums) {
17         if(available(nums,0))
18             return true;
19         return false;
20     }
21 };

法2：正向循环每个下标元素，找出每个下标所能移动到最远位置+1；最后看最远位置+1是否>=nums.size()；

 1 class Solution {
 2 public:
 3     bool canJump(vector<int>& nums) {
 4         int reach=1;
 5         for(int i=0;i<reach && reach < nums.size();i++){
 6             reach = max(reach,nums[i]+i+1);
 7         }
 8         return reach>=nums.size();
 9         }
10 };

法3：逆向，从最高层下楼梯，一层一层下降，看最后能不能下降到第0层。

 1 class Solution {
 2 public:
 3     bool canJump(vector<int>& nums) {
 4         int lastPos=nums.size()-1;
 5         for(int i=nums.size()-1;i>=0;i--)
 6         {
 7             if(i+nums[i]>=lastPos){
 8                 lastPos=i;
 9             }
10         }
11         return lastPos==0;
12     }
13 };

法4：动规，再续。