时间轴

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;
    }
};