每日一题：跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是2。
从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <=
• 0 <= nums[i] <= 1000
• 题目保证可以到达 nums[n-1]

---

分解题目：

• 目标：求解跳到最后一个位置的最小跳跃数
• 依赖于：存在一个位置能跳到最后一个位置（题目已经保证此项）
                跳到这个位置的最小跳跃数。
• 如果用 i 来表示最后一次跳跃，i - 1表示的倒数第二次跳跃，很明显，求解 i 的最小跳跃数可以转换为求解 i - 1的最小跳跃数。

至此，可以用动态规划进行解决。

定义：dp[ i ]表示跳跃到第 i 个位置的最小跳跃数。dp[n - 1]即为所求，边界值dp[0] = 0。

对于第 i 个位置，可能有多个前置的位置可以跳跃到达，我们需要找到其中的最小值，即：

j from 0 to i
if(nums[j]+j>i)  dp[i]=min(dp[i],dp[j]+1); 

完整代码：

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,n);
        dp[0] = 0;
        for(int i = 1;i < n;++i){
            for(int j = 0; j < i;++j){
                if(nums[j] + j >= i){
                    dp[i] = min(dp[i],dp[j] + 1);
                }
            } 
        }
        return dp[n-1];
    }
};

然而这里的动态规划反而引入了更多的重复计算。

如果换成贪心算法：

class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0;
        int end = 0;
        int farthest = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            farthest = max(farthest, nums[i] + i);
            if (i == end) {
                jumps++;
                end = farthest;
                if (end >= nums.size() - 1) {
                    break;
                }
            }
        }
    return jumps;
    }
};

• jumps是跳跃的次数，end是当前的终点，farthest是当前点跳跃能够到达的最远点。
• 遍历数组，除了最后一个元素，因为最后一个元素的位置不需要跳跃，自己就能到达自己。
• 我们时刻维护从当前点到达的最远距离，当我们到达了当前终点，就把最远距离设置成终点，这里体现贪心的思想。
• 同时，当到达了end时，也说明需要进行一次跳跃。

即：每次在上次能跳到的范围（i，end）内选择一个能跳的最远的位置（也就是能跳到farthest位置的点）作为下次的起跳点。

对于初学者，这看上去非常的反直觉，这是不是局部最优？为什么是全局最优？如果出现当前跳的最远，但是下下步跳得近了怎么办？

这里需要理解end的作用，如果把end抽象成一个分隔符，所谓跳跃过程就是在数组内插入分隔符的过程，使最终分出的子数组数量最小。

而fareset的作用是，保留上一个end到当前end这个区间范围内可以达到的最远值。

注意区间范围这个点。

在贪心算法中，每一步的end都是当前范围能到达的最远点，也即最大值farest，所以最终分出的间隔就会更少。

下面用一个具体图例做进一步解释，初始状态，进行第一次跳跃：

 跳跃后在区间内遍历维护最远值farest：

这里有人可能会说，看起来像恰好1就跳到了较大值10。那如果我们把这里的1换成0会发生什么？

可以看到维护的farest，才是起到关键作用的值。和nums[end]中的值并无全部关系。 这也是上面提到的，保留上一个end到当前end这个区间范围内可以达到的最远值。

图中箭头描述的是end变化的过程，真实的跳跃过程和end的变化过程数量相同，但是路径不一定相同。（每条end箭头仅对应一条跳跃，比如这里是从2跳到3跳到10。）

继续遍历：

只要理解了end表示间隔且和真实跳跃一一对应，farest表示一个区间内跳到的最远距离这两个概念，这里的贪心算法就很好理解了。