045 Jump Game II 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的首位。
数组中的每个元素表示你在该位置的最大跳跃长度。
你的目标是用最小跳跃次数到达最后一个索引。
例如:
给定一个数组 A = [2,3,1,1,4]
跳到最后一个索引的最小跳跃数是 2。(从索引 0 跳到 1 跳1步，然后跳3步到最后一个索引。)
注意:
假设你总是可以到达最后一个索引位置。
详见：https://leetcode.com/problems/jump-game-ii/description/

Java实现：

curReach是维护的当前能跳到的最大位置，maxReach是指从之前的点能到达到得最远位置。
当i 大于之前点能跳到的最大位置时，就需要跳一步，并把curReach更新为maxReach。
最后返回若是curReach能到最后一个元素，就返回step, 若是到不了，就说明根本走不到最后一步，返回0。

参考：http://www.cnblogs.com/Dylan-Java-NYC/p/4834079.html

class Solution {

    public int jump(int[] nums) {

        int n=nums.length;

        int step=0;

        int curReach=0;

        int maxReach=0;

        for(int i=0;i<n;++i){

            if(curReach<i){

                ++step;

                curReach=maxReach;

            }

            maxReach=maxReach>(nums[i]+i)?maxReach:(nums[i]+i);

        }

        return maxReach<n-1?0:step;

    }

}

C++实现：

class Solution {

public:

    int jump(vector<int>& nums) {

        int n=nums.size();

        int res=0;

        int curRch=0;

        int maxRch=0;

        for(int i=0;i<n;++i)

        {

            if(curRch<i)

            {

                ++res;

                curRch=maxRch;

            }

            maxRch=max(maxRch,nums[i]+i);

        }

        return res;

    }

};

参考：http://www.cnblogs.com/ganganloveu/p/3761715.html