LeetCode --- 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.)

尝试着用英文来写题解，用英文给代码加注释！有很多事情看上去很难，如果一直退缩着，

就永远还是只会惊呼那些做到的人那么的牛逼，倒不如现在就狠下心来逼上自己一把！

附上代码：

 1 class Solution {
 2 public:
 3     int jump(int A[], int n) {
 4         // last: keep the track of the maximum distance
 5         // that has been reached by using "cnt" steps
 6         // whereas next is the maximum distance that
 7         // can be reached by using "cnt+1" steps
 8         // thus next = MAX(A[i]+i) where 0 <= i <= last
 9         int last = 0, cnt = 0, next = 0;
10         for (int i = 0; i < n; i++) {
11             if (i > last) {
12                 // if "last" is not n-1 and 
13                 // can't go further(which means last >= next)
14                 // return -1 represents never reach the end
15                 if (last >= next && last < n-1) {
16                     return -1;
17                 }
18                 cnt++;
19                 last = next;
20             }
21             next = max(next, A[i]+i);
22         }
23         return cnt;
24     }
25 };