# 5.7 如何运用贪心思想玩跳跃游戏

本文对应的力扣题目：

# 5.7.1 跳跃游戏 I

函数签名如下：

bool canJump(vector<int>& nums);

贪心思路：

bool canJump(vector<int>& nums) {
    int n = nums.size();
    int farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        // 不断计算能跳到的最远距离
        farthest = max(farthest, i + nums[i]);
        // 可能碰到了 0，卡住跳不动了
        if (farthest <= i) return false;
    }
    return farthest >= n - 1;
}

1
2
3
4
5
6
7
8
9
10
11

# 5.7.2 跳跃游戏 II

函数签名如下：

int jump(vector<int>& nums);

动态规划思路：

// 备忘录
vector<int> memo;
/* 主函数 */
int jump(vector<int>& nums) {
    int n = nums.size();
    // 备忘录都初始化为 n，相当于 INT_MAX
    // 因为从 0 跳到 n - 1 不会超过 n - 1 步
    memo = vector<int>(n, n);
    return dp(nums, 0);
}

/* 返回从索引 p 跳到最后一格需要的最少步数 */
int dp(vector<int>& nums, int p) {
    int n = nums.size();
    // base case
    if (p >= n - 1) {
        return 0;
    }
    // 子问题已经计算过
    if (memo[p] != n) {
        return memo[p];
    }
    int steps = nums[p];
    // 穷举每一个选择
    // 你可以选择跳 1 步，2 步...nums[p] 步
    for (int i = 1; i <= steps; i++) {
        // 计算每一个子问题的结果
        int subProblem = dp(nums, p + i);
        // 取其中最小的作为最终结果
        memo[p] = min(memo[p], subProblem + 1);
    }
    return memo[p];
}

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

贪心思路：

int jump(vector<int>& nums) {
    int n = nums.size();
    // 站在索引 i，最多能跳到索引 end
    int end = 0;
    // 从索引 [i..end] 起跳，最远能到的距离
    int farthest = 0;
    // 记录跳跃次数
    int jumps = 0;
    for (int i = 0; i < n - 1; i++) {
        farthest = max(nums[i] + i, farthest);
        if (end == i) {
            jumps++;
            end = farthest;
        }
    }
    return jumps;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

← 相同的数