题目内容

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

假设你总是可以到达数组的最后一个位置。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例

示例 1:

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

示例 2:

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

提示

1 <= nums.length <= 1000
0 <= nums[i] <= 10^5

题解

本题使用动态规划+贪心算法求解。

首先，令f[i]为起点跳到i的最小步数，那么我们会发现f[i]是具有单调性的，也就是f[i + 1] >= f[i]。用反证法：假设f[i + 1] < f[i]，不妨设从k,(k <= i)点跳到i + 1，即：k + nums[k] >= i + 1，那么k + nums[k]也必然大于i，此时：f[i + 1] = f[i]。如果nums数组每一项都为1，则：f[i + 1] > f[i]，综上：f[i + 1] >= f[i]，与假设矛盾，因此f[i]具有单调递增性。

因此f[i]中的数值就会就变成类似：0 1…1 2…2 3…3 ……的情况，在动态规划时瓶颈就在于更新每个点的最小值时需要遍历所有能跳到i的点，而有了单调性以后就可以用第一个能跳到i的点更新了，因为无论是取哪一个点跳到i，其最终的结果是一样的，但是取第一个点和取最后一个点所需要的步数可能不相同，所以尽量选择靠前的点，这样步数就可能会减少，这就利用了贪心的思想。

代码

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