0055. Jump Game

题目信息

题号:
  1. 跳跃游戏

难度:

Medium

主题:

数组、动态规划、贪心、可达区间

原题:

LeetCode 0055

重点:

从枚举所有落点序列,推导到只维护可达前缀的最右边界

题目重述

给定一个非负整数数组 nums。开始时位于下标 0;位于下标 i 时,可以向右跳到任意满足 i < next <= i + nums[i] 的下标。

判断是否能够到达最后一个下标。数组只有一个元素时,起点已经是终点。

约束为 1 <= nums.length <= 10^4、0 <= nums[i] <= 10^5。

自建示例

输入:nums = [2,0,2,0,1]
输出:true
解释:可以按 0 -> 2 -> 4 到达终点。
输入:nums = [3,2,1,0,4]
输出:false
解释:下标 0 到 3 可达,但这些位置都无法把范围扩展到下标 4。
输入:nums = [0]
输出:true
解释:起点已经是终点,不需要跳跃。

C++ 实现

#include <algorithm>
#include <vector>

class Solution {
private:
    bool exhaustiveDfs(const std::vector<int>& nums, int index) {
        const int last = static_cast<int>(nums.size()) - 1;
        if (index == last) {
            return true;
        }

        const int end = std::min(last, index + nums[index]);
        for (int next = index + 1; next <= end; ++next) {
            if (exhaustiveDfs(nums, next)) {
                return true;
            }
        }
        return false;
    }

    bool exhaustiveSearch(const std::vector<int>& nums) {
        return exhaustiveDfs(nums, 0);
    }

    bool explicitReachability(const std::vector<int>& nums) {
        const int n = static_cast<int>(nums.size());
        std::vector<char> reachable(n, false);
        reachable[0] = true;

        for (int index = 0; index < n; ++index) {
            if (!reachable[index]) {
                continue;
            }

            const int end = std::min(n - 1, index + nums[index]);
            for (int next = index + 1; next <= end; ++next) {
                reachable[next] = true;
            }
        }
        return reachable[n - 1];
    }

    bool farthestReach(const std::vector<int>& nums) {
        const int last = static_cast<int>(nums.size()) - 1;
        int farthest = 0;

        for (int index = 0; index <= last; ++index) {
            if (index > farthest) {
                return false;
            }

            const int reach = std::min(last, index + nums[index]);
            farthest = std::max(farthest, reach);
            if (farthest == last) {
                return true;
            }
        }
        return true;
    }

public:
    bool canJump(std::vector<int>& nums) {
        return farthestReach(nums);
    }
};

题解

落点枚举基线

从下标 index 出发,可以枚举区间 [index + 1, min(last, index + nums[index])] 中的每个落点,再递归判断后续是否可达。

任意合法路径的下一跳都在该区间中,所以完整枚举不会漏解。到达最后一个下标时返回真;若所有分支都失败, 当前状态才失败。

不同路径可能反复到达同一个下标,而“从该下标能否到终点”与此前路径无关。直接递归会重复展开相同后缀, 最坏产生指数级搜索树。

显式可达状态

把重复状态改为从左到右传播可达性:

reachable[i] = 是否存在一条从 0 到 i 的路径

reachable[0] 为真。若 i 可达,则它能到达的整个右侧区间都应标记为真。

这种动态规划把每个下标是否可达保存一次,却仍可能从许多起点反复写入同一段区间。最坏情况下,前面的每个位置 都能覆盖大量后继,时间仍为 O(n^2),并使用 O(n) 状态数组。

可达前缀不变量

显式状态还包含更强的结构:可达位置始终构成连续前缀。

初始可达集合是 [0, 0]。若已经确认 [0, farthest] 全部可达,扫描其中任意下标 i 时, 它新增的覆盖范围为 [i + 1, i + nums[i]]。这个区间从现有前缀内部或紧邻右侧开始,与原前缀合并后 仍然是前缀,只会改变最右端点。

因此进入每次循环时保持:

[0, farthest] 中的所有下标都可达
farthest 是此前已处理可达位置能够覆盖的最右下标

当 index <= farthest 时,当前位置真实可达,可以安全更新:

farthest = max(farthest, index + nums[index])

代码把结果截断到 last,因为超过终点的距离不再提供额外信息。

当 index > farthest 时,此前所有可达位置都无法到达 index。更右侧位置也不可能被跨越后突然到达: 若某个可达位置能够跳到更远的 next,由于跳跃距离可以小于上限,它也必然能够先到达 index。 因此第一个断点出现后即可返回 false,而断点右侧的 nums 值没有资格参与边界扩展。

算法也不需要选择具体落点。它等价于把所有已知可达位置的跳跃区间取并集,并只保留并集右端点。 任意真实路径经过的落点都在这个前缀内,扫描到它时,其跳跃能力自然会参与更新。

状态演化

对 nums = [3,2,1,0,4]:

下标

旧 farthest

当前覆盖终点

新 farthest

0

0

3

3

1

3

3

3

2

3

3

3

3

3

3

3

4

3

不可达,不能使用 nums[4]

失败

下标 4 的值虽然很大,但到达该位置本身尚未成立,因此不能用它扩展范围。

边界情况

单元素数组初始时 farthest == last == 0,公开方法在扫描第一个位置后立即返回真。

值为 0 的位置不一定形成障碍。只要此前某个可达位置已经把边界扩展到它之后,扫描仍可继续;只有最远边界 停在某个位置且无法再向右扩展时,才会形成断点。

本题只判断可达性,一个最远边界已经足够。若要求最少跳跃次数,还必须区分“当前跳数覆盖到哪里”和 “再跳一次覆盖到哪里”,不能压缩成单一边界。

复杂度分析

朴素递归最坏为指数级时间,递归深度为 O(n)。显式可达状态最坏为 O(n^2) 时间、O(n) 空间。

主方法顺序扫描一次,每个位置只做常数次比较和更新,时间为 O(n),额外空间为 O(1)。