博文中会简要介绍Leetcode P0045题目分析及解题思路。

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

Example:

Input: [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.

这道题不再赘述动态规划的解法，主要讲解贪心算法。贪心算法，顾名思义，就是贪婪地选取最大/最小/最优解等这种最值解，从而最终获取题目的最优解。一般来说，想要使用贪心算法，需要证明贪心算法通过选择最值一定能选取到最优解，有的题目相对好证明，有的证明繁琐。证明繁琐的题目可以谨慎使用贪心算法，优先考虑动态规划。

那么这道题如何使用贪心算法呢？根据贪心算法的定义，我们知道在每次迭代中，我们都应该选择最值解，在这道题里我们应该选择什么最为最值解呢？观察题目不难发现，要想找到跳到终点的最少步数，我们应当尽可能选择那些能跳的更远甚至最远的位置。我们能跳的更远，那么所用的步数相应的也会更少。

我们比较直观地可以获得这样的结论，证明步骤在这篇博文里就略述一二。我们可以想象一个极端情况，一个位置可以直接跳到终点而这个位置后的任意位置都不可以直接跳到终点，并且跳到这个位置和跳到它后面的位置所花费的步数是一样的。那么可想而知，我们选择这个跳到终点（最远）的位置显然会让我们花费更少的步数。

那么由此可得，我们在遍历的时候，right指针指向当前我们已经能够到达的所有位置里，能够跳到的最远位置。一旦right指针大于终点，即意味着我们可以只跳一次就能到终点，则推出循环；其余时间不断更新right指针。

以下是Java的题解代码实现。

class Solution {
    // Greedy的时间复杂度是O(n)
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        
        int left = 1, right = nums[0], steps = 0;
        while (right < nums.length-1) {
            int nextMaxRight = right;
            while (left <= right) {
                nextMaxRight = Math.max(nextMaxRight, left+nums[left]);
                ++left;
            }
            
            ++steps;
            right = nextMaxRight;
        }
        
        ++steps;
        return steps;
    }

    // 也可以用动态规划，但是时间复杂度是O(n^2)
    /**
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1)
            return 0;
        
        int left = 1, right = nums[0], steps = 0;
        while (right < nums.length-1) {
            int nextMaxRight = right;
            while (left <= right) {
                nextMaxRight = Math.max(nextMaxRight, left+nums[left]);
                ++left;
            }
            
            ++steps;
            right = nextMaxRight;
        }
        
        ++steps;
        return steps;
    }
    */
}

以下是C++的题解代码实现。

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() <= 1)
            return 0;
        
        int left = 1, right = nums[0], steps = 0;
        while (right < nums.size()-1) {
            int max_right = right;
            while (left <= right) {
                max_right = max(max_right, left+nums[left]);
                ++left;
            }
            
            ++steps;
            right = max_right;
        }
        
        ++steps;
        return steps;
    }
};