题目描述

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

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

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

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

样例

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

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

限制

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

算法1

(动态规划，贪心) $O(n)$

1. 设状态 $f(i)$ 表示到达 $i$ 所需要的最少步数。
2. $f(0) = 0$，其余待定。定义辅助指针 $last$ 为第一次到达 $i$ 时上一步的位置，$last$ 从 $0$ 开始。
3. 通过归纳可以得知，从小到大遍历过程中，第一次通过 $x$ 可以到达 $y$ 时，$y$ 的最少步数就是 $x$ 的最少步数加 $1$。因为一次移动，可以从 $x$ 到 $[x + 1, x + nums(x)]$ 的任意位置，所以根据归纳（即 $x$ 也是这样到达的），这样一定是最优的。
4. 根据以上得知，令 $f(i) = f(last) + 1$ 后，$f(i)$ 就会是最优值。
5. 故可以根据 $i$ 来让 $last$ 向后移动，找到最早的可以一步到达 $i$ 的位置，然后根据 $f(last)$ 更新 $f(i)$。

时间复杂度

• 数组的每个元素最多被遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    int jump(vector<int>& nums) {
        const int n = nums.size();
        vector<int> f(n);
        f[0] = 0;
        int last = 0;

        for (int i = 1; i < n; i++) {
            // 依次求 f[i] 的值。
            while (i > last + nums[last]) // 根据 i 来更新 last。
                last++;

            f[i] = f[last] + 1; // 根据 f[last] 更新 f[i]。
        }

        return f[n - 1];
    }
};

算法2

(贪心，双指针) $O(n)$

1. 定义指针 $cur$ 和 $dis$，分别表示当前位置和可达到的最远位置。定义一轮遍历过程如下：
   • 移动 $cur$ 到 $dis$，途中记录可以达到的最远位置 $next$。
   • 答案加 $1$。
   • 更新 $dis$ 为 $next$。
2. 当 $dis$ 大于等于 $n-1$ 时视为到达，返回答案。

时间复杂度

• 数组的每个元素最多被遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int jump(vector<int>& nums) {
        const int n = nums.size();
        int ans = 0, cur = 0, dis = 0;

        while (dis < n - 1) {
            int next = 0;
            while (cur <= dis) {
                next = max(next, cur + nums[cur]);
                cur++;
            }

            ans++;
            dis = next;
        }

        return ans;
    }
};