题目链接：Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example: Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
这道题的要求是给定一整数数组，数组元素表示每次可以跳跃的最大距离。然后初始位置在数组的第一个元素，目的是以最少的步数到达最后元素。
这道题是Jump Game II，是其Jump Game的扩展。
在Jump Game中，采用贪心的思路，采用reach变量维护能到达最远处，即为全局最优解。当遍历到i的时候，局部最优解为A[i]+i，因此，此时的全局最优解即为reach和A[i]+i的最大值：reach = max(reach, A[i] + i)。
而这道题，需要求的是最少的步数。因此需要添加step变量记录最少步数。至于什么时候step需要加1？答案是当前的i超过了前一步的最远位置。所以引入last变量记录上一步能到达的最远位置。reach、step、last的初始值均为0。当遍历到i的时候，如果i超过了last（即上一步能到达的最远位置），说明步数需要加1（即step++），此时仍需要更新last为当前最远位置reach。全程只需遍历1次数组，而且空间复杂度为常量。
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution
{
public:
int jump(int A[], int n)
{
int reach = 0, last = 0, step = 0;
for(int i = 0; i <= reach && i < n; ++ i)
{
if(i > last)
{
++ step;
last = reach;
}
reach = max(reach, A[i] + i);
}
return reach >= n - 1 ? step : 0;
}
};