Jump Game II

LeetCode #45

Description:

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.

Example:

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

Note:
You can assume that you can always reach the last index.

Idea:

这个很难。

要理解这个算法，首先明白，这个题只要我们求跳数，怎么跳，最后距离是多少，都没让求的。

大牛这个算法的思想主要是，扫描数组（废话。。。），以确定当前最远能覆盖的节点，放入curr。然后继续扫描，直到当前的路程超过了上一次算出的覆盖范围，那么更新覆盖范围，同时更新跳数，因为我们是经过了多一跳才能继续前进的。

http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html

curr_max是每步更新的最远距离，last_max是之前step最远能跳的，如果现在index没达到last_max就不用更新，否则，更新到curr_max.

time complexity: O(n).

Code:

class Solution {
public:
    int jump(vector<int>& nums) {
        int steps=0;
        int curr_max=0;
        int last_max=0;

        for(int i=0; i<nums.size(); ++i){
            if(i>last_max){
                last_max=curr_max;
                steps++;
            }

            curr_max=max(curr_max, i+nums[i]);
        }

        return steps;
    }
};