Jump Game

题目描述：

给定一个非负的整数数组，起点为数组的第一个位置，每一个数组元素的值表示从该位置能向前跳的最大值，判断能否到达该数组的最后一个位置。例如：A = [2,3,1,1,4], 从第一个位置开始该数为2向前跳2，到达第三个位置，该数为1向前跳1，到达第四个位置，该数为1向前跳1，到达最后一个位置，所以返回true。A = [3,2,1,0,4]，从一个位置开始，该数为3向前跳3，到达第四个位置，该数为0无法向前跳，再从第二个位置开始，同理最后也只能到第四个位置，所以返回false。

分析：当nums[i]==0&&sum<i+1时，其中i表示当前位置，sum表示最大到达的位置，此时就像上述例子，只能停留在第四个位置。每次当nums[i]+i>sum,且nums[i]不为0时，我们都要更新sum值，sum=nums[i]+i。具体代码如下：

 1 bool canJump(vector<int>& nums) {
 2         int n=nums.size(),sum=0;
 3         if(n<=1) return true;
 4         for(int i=0;i<n-1;i++)
 5         {
 6             if(nums[i]==0&&sum<i+1) return false;
 7             if(nums[i]+i>sum&&nums[i]>0)
 8             {
 9                 sum=nums[i]+i;
10                 if(sum>=n-1) return true;
11             }
12         }
13         return false;
14     }

在上题的基础上，我们要求求出到达最后一个位置所跳最少的步数。例如A = [2,3,1,1,4]，从第一个位置跳到第二的位置，然后可以直接跳到最后一个位置，最少步数为2.

分析：我们用一个变量count记录跳跃的步数，用变量last和cur分别记录上一次跳跃的最远距离和当前一次跳跃的最远距离，在循环遍历时，只有在i等于last记录数时，count才加1，当cur记录数大于等于数组最后一个位置时，返回count+1,当无法达到最后一个位置时返回-1.

 1 int jump(vector<int>& nums) {
 2          int step_count = 0;
 3          int last_jump_max = 0;
 4          int current_jump_max = 0;
 5          int length = nums.size();
 6          if (length <= 1) return 0;
 7          for (int i = 0; i<length; i++)
 8          {
 9            current_jump_max = max(current_jump_max, i + nums[i]);    
10            if (current_jump_max >= length - 1)
11                 return step_count+1;
12            else
13            {
14             if (i == last_jump_max)
15             {
16                 step_count++;
17                 last_jump_max = current_jump_max;
18             }
19            }
20          }
21          return -1;
22     }