0055. Jump Game =============== 题目信息 -------- :题号: 0055. 跳跃游戏 :难度: Medium :主题: 数组、动态规划、贪心、可达区间 :原题: `LeetCode 0055 `_ :重点: 从枚举所有落点序列,推导到只维护可达前缀的最右边界 题目重述 -------- 给定一个非负整数数组 ``nums``。开始时位于下标 ``0``;位于下标 ``i`` 时,可以向右跳到任意满足 ``i < next <= i + nums[i]`` 的下标。 判断是否能够到达最后一个下标。数组只有一个元素时,起点已经是终点。 约束为 ``1 <= nums.length <= 10^4``、``0 <= nums[i] <= 10^5``。 自建示例 -------- .. code-block:: text 输入:nums = [2,0,2,0,1] 输出:true 解释:可以按 0 -> 2 -> 4 到达终点。 .. code-block:: text 输入:nums = [3,2,1,0,4] 输出:false 解释:下标 0 到 3 可达,但这些位置都无法把范围扩展到下标 4。 .. code-block:: text 输入:nums = [0] 输出:true 解释:起点已经是终点,不需要跳跃。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool exhaustiveDfs(const std::vector& nums, int index) { const int last = static_cast(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& nums) { return exhaustiveDfs(nums, 0); } bool explicitReachability(const std::vector& nums) { const int n = static_cast(nums.size()); std::vector 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& nums) { const int last = static_cast(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& nums) { return farthestReach(nums); } }; 题解 ---- 落点枚举基线 ~~~~~~~~~~~~ 从下标 ``index`` 出发,可以枚举区间 ``[index + 1, min(last, index + nums[index])]`` 中的每个落点,再递归判断后续是否可达。 任意合法路径的下一跳都在该区间中,所以完整枚举不会漏解。到达最后一个下标时返回真;若所有分支都失败, 当前状态才失败。 不同路径可能反复到达同一个下标,而“从该下标能否到终点”与此前路径无关。直接递归会重复展开相同后缀, 最坏产生指数级搜索树。 显式可达状态 ~~~~~~~~~~~~ 把重复状态改为从左到右传播可达性: .. code-block:: text reachable[i] = 是否存在一条从 0 到 i 的路径 ``reachable[0]`` 为真。若 ``i`` 可达,则它能到达的整个右侧区间都应标记为真。 这种动态规划把每个下标是否可达保存一次,却仍可能从许多起点反复写入同一段区间。最坏情况下,前面的每个位置 都能覆盖大量后继,时间仍为 ``O(n^2)``,并使用 ``O(n)`` 状态数组。 可达前缀不变量 ~~~~~~~~~~~~~~ 显式状态还包含更强的结构:可达位置始终构成连续前缀。 初始可达集合是 ``[0, 0]``。若已经确认 ``[0, farthest]`` 全部可达,扫描其中任意下标 ``i`` 时, 它新增的覆盖范围为 ``[i + 1, i + nums[i]]``。这个区间从现有前缀内部或紧邻右侧开始,与原前缀合并后 仍然是前缀,只会改变最右端点。 因此进入每次循环时保持: .. code-block:: text [0, farthest] 中的所有下标都可达 farthest 是此前已处理可达位置能够覆盖的最右下标 当 ``index <= farthest`` 时,当前位置真实可达,可以安全更新: .. code-block:: text farthest = max(farthest, index + nums[index]) 代码把结果截断到 ``last``,因为超过终点的距离不再提供额外信息。 当 ``index > farthest`` 时,此前所有可达位置都无法到达 ``index``。更右侧位置也不可能被跨越后突然到达: 若某个可达位置能够跳到更远的 ``next``,由于跳跃距离可以小于上限,它也必然能够先到达 ``index``。 因此第一个断点出现后即可返回 ``false``,而断点右侧的 ``nums`` 值没有资格参与边界扩展。 算法也不需要选择具体落点。它等价于把所有已知可达位置的跳跃区间取并集,并只保留并集右端点。 任意真实路径经过的落点都在这个前缀内,扫描到它时,其跳跃能力自然会参与更新。 状态演化 ~~~~~~~~ 对 ``nums = [3,2,1,0,4]``: .. list-table:: :header-rows: 1 * - 下标 - 旧 ``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)``。