45. Jump Game II

Given an array of non-negative integers nums, 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.

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

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: 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.
Example 2:

Input: nums = [2,3,0,1,4]
Output: 2
 

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 105

这题其实可以转化为一个数学问题。我们需要遍历在本次格子上所有的可能性，并且算出当前移动的格子数量和移动到的格子数量之和，取所有移动到的格子中最大的那个，找出后我们也就移动到了最大的和的格子之上。

重复进行移动判断，那么我们就能得出最优解。

class JumpGameII : public Solution {
public:
    void Exec() {

    }
    int jump(vector<int>& nums) {
        int jump = 0, curAt = 0;
        while (curAt != nums.size() - 1) {
            int value = 0, nextAt = curAt;
            for (int i = curAt + 1; i <= curAt + nums[curAt]; i++) {
                if (i == nums.size() - 1) return ++jump;
                int cur = i - curAt + nums[i];
                if (cur > value) {
                    value = cur;
                    nextAt = i;
                }
            }
            ++jump; curAt = nextAt;
        }
        return jump;
    }
};