时间轴

2025-10-02

init

题目：

P45 跳跃游戏II

https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

我最先想到的是动态规划
令 dp[i] 表示到达 i 的最小跳跃次数，-1 表示不可达，那么对于 0 <= j < i，如果 j 可以到达 i ,即 nums[j] + j >= i 且 dp[j] != -1

$$
dp[i] = min (dp[j] +1)
$$

如果没有可达的 j 那么

$$
dp[i] = -1
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <climits>
#include <vector>
using std::vector;

class Solution {
public:
  int jump(vector<int> &nums) {
    // dp[i]表示到达i的最小跳跃次数,-1表示不可达
    // 对于 0<=j <i
    // if(nums[j] + j >= i ) dp[i] = dp[j] + 1;
    // 如果不存在这样的j,dp[i] = -1;
    int n;
    int min;
    n = nums.size();
    vector<int> dp(n, -1);

    dp[0] = 0;
    for (int i = 1; i < n; i++) {
      min = INT_MAX;
      for (int j = 0; j < i; j++) {
        if (nums[j] + j >= i && dp[j] != -1 && dp[j] + 1 < min) {
          min = dp[j] + 1;
        }
      }
      if (min != INT_MAX) {
        dp[i] = min;
      } else {
        dp[i] = -1;
      }
    }
    return dp[n - 1];
  }
};

这道题其实是经典的贪心题，从后往前看，最后一个位置一定是之前某个位置跳过来的，但是这个之前的位置可能有多个，那么我们就贪心地选择最远的那个(因为反正都是多一步，选择离起点更近的必定能减少跳跃次数，这因为如果两个点都能到达最后一个位置，a 的位置靠前，b 的位置靠后，那么我们肯定会选择 a，因为到达 a 的 step 必定小于等于 b 的 step)。选择后，选择的这个位置就成了新的最后一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int jump(vector<int>& nums) {
        int position = nums.size() - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
};

也可以用下面这道题的思路改造

P55 跳跃游戏

https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

官方题解：

如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。

例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。

从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。

fig1

在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int jump(vector<int>& nums) {

        int i = 0, j = 0, n = nums.size();

        int max_pos = 0;
        int last_end = 0;
        int step = -1;

        for(i = 0; i< n;i++){
            max_pos = std::max(max_pos, i + nums[i]);
            if(i == last_end){
                last_end = max_pos > n-1 ? n-1: max_pos;
                step++;
            }
        }
        return step;

    }
};

leetcode hot 100 rewrite

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <vector>
using std::vector;

class Solution {
    public:
        int jump(vector<int> &nums)
        {
                // 从后往前跳，贪心地选择最远的那个能跳过来的
                int i, n = nums.size();
                int curr = n - 1;
                int cnt = 0;

                while (curr > 0) {
                        for (i = 0; i < curr; i++) {
                                if (nums[i] + i >= curr){
                                        curr = i;
                                        cnt++;
                                        break;
                                }

                        }
                }

                return cnt;
        }
};