0045. Jump Game II ================== 题目信息 -------- :题号: 0045. 跳跃游戏 II :难度: Medium :主题: 数组、动态规划、BFS 分层、区间贪心 :原题: `LeetCode 0045 `_ :重点: 从枚举所有跳法,推导到用当前层右端和下一层最远右端计算最少跳数 题目重述 -------- 给定一个非负整数数组 ``nums``。站在下标 ``i`` 时,可以向右跳到任意满足以下条件的下标 ``next``: .. code-block:: text i < next <= i + nums[i] 从下标 ``0`` 出发,返回到达最后一个下标所需的最少跳跃次数。题目保证最后一个下标一定可以到达。 ``nums`` 的长度位于 ``[1, 10^4]``,每个元素位于 ``[0, 1000]``。 自建示例 -------- 需要比较同一层的多个起点: .. code-block:: text 输入:nums = [2, 3, 1, 1, 4] 输出:2 解释:第一跳可以到下标 1 或 2。选择下标 1 后,第二跳可以直接到达下标 4。 不能把当前落点最远当成最终选择: .. code-block:: text 输入:nums = [2, 3, 0, 1, 4] 输出:2 解释:若第一跳只看落点最远,会跳到下标 2 并停住;正确路线是 0 -> 1 -> 4。 单元素数组: .. code-block:: text 输入:nums = [0] 输出:0 解释:起点已经是终点,不需要跳跃。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int exhaustiveFrom(const std::vector& nums, int index) { const int n = static_cast(nums.size()); if (index >= n - 1) { return 0; } const int unreachable = INT_MAX / 4; int best = unreachable; const int farthest = std::min(n - 1, index + nums[index]); for (int next = index + 1; next <= farthest; ++next) { const int suffix = exhaustiveFrom(nums, next); if (suffix != unreachable) { best = std::min(best, suffix + 1); } } return best; } int exhaustiveSearch(const std::vector& nums) { return exhaustiveFrom(nums, 0); } int quadraticDynamicProgramming(const std::vector& nums) { const int n = static_cast(nums.size()); const int unreachable = INT_MAX / 4; std::vector minimumJumps(n, unreachable); minimumJumps[0] = 0; for (int index = 0; index < n; ++index) { if (minimumJumps[index] == unreachable) { continue; } const int farthest = std::min(n - 1, index + nums[index]); for (int next = index + 1; next <= farthest; ++next) { minimumJumps[next] = std::min( minimumJumps[next], minimumJumps[index] + 1 ); } } return minimumJumps[n - 1]; } int intervalBreadthFirstSearch(const std::vector& nums) { const int n = static_cast(nums.size()); if (n == 1) { return 0; } int jumps = 0; int currentEnd = 0; int nextEnd = 0; for (int index = 0; index < n - 1; ++index) { nextEnd = std::max(nextEnd, index + nums[index]); if (index == currentEnd) { ++jumps; currentEnd = nextEnd; if (currentEnd >= n - 1) { break; } } } return jumps; } public: int jump(std::vector& nums) { return intervalBreadthFirstSearch(nums); } }; 题解 ---- 完整跳法枚举 ~~~~~~~~~~~~ 从下标 ``index`` 出发,可以选择区间 ``[index + 1, index + nums[index]]`` 中的任意位置。最直接的递归为: .. code-block:: text answer(index) = 1 + min(answer(next)) 任意合法路线的第一跳都位于这个区间中,因此枚举不会漏解;递归到最后一个下标时,剩余跳数为零。 不同路线会反复到达同一下标。例如从下标 0 跳到 1 或 2,之后都可能到达 3,从 3 开始的后续搜索会被重复计算。 直接递归的分支数最坏呈指数增长。 下标动态规划 ~~~~~~~~~~~~ 令 ``minimumJumps[i]`` 表示从起点到达下标 ``i`` 的最少跳数。初始状态为: .. code-block:: text minimumJumps[0] = 0 从一个已到达位置 ``i`` 出发,值 ``minimumJumps[i] + 1`` 可以传播到它右侧的整个可达区间。所有边都只向右,按 下标从左到右处理时,当前位置的所有前驱都已经被考虑。 动态规划把每个下标的最优值保存下来,删除了重复后缀搜索。它仍可能从许多起点反复更新同一段区间,最坏时间为 ``O(n^2)``。继续优化需要利用“每次跳跃覆盖的是连续区间”这一结构。 分层覆盖模型 ~~~~~~~~~~~~ 把每个下标看成图节点,从 ``i`` 向所有可跳到的位置连一条代价为 1 的边。最少跳数就是无权图最短路,BFS 会按 跳数分层访问节点。 本题无需保存整层队列。若不超过 ``k`` 次跳跃可以到达最远下标 ``r``,那么 ``[0, r]`` 内的所有位置也都可以在 不超过 ``k`` 次跳跃内到达,因为每次可以选择不超过上限的任意正跳跃距离。因此每层可达集合只需记录一个右端点。 三个变量分别表示: * ``jumps``:已经提交的跳跃次数; * ``currentEnd``:使用 ``jumps`` 次跳跃能够覆盖的最远下标; * ``nextEnd``:从当前层所有位置再跳一次能够覆盖的最远下标。 扫描 ``index <= currentEnd`` 的所有位置时,持续更新: .. code-block:: text nextEnd = max(nextEnd, index + nums[index]) 到达 ``index == currentEnd`` 时,当前层的所有出边都已检查完。此时才提交下一跳: .. code-block:: text jumps += 1 currentEnd = nextEnd 算法并未提前选择某个具体落点,而是完整比较当前层所有起点的扩展能力,再保留下一层的最远边界。 分层覆盖不变量 ~~~~~~~~~~~~~~ 每次开始扫描一层时,保持以下状态: * ``[0, currentEnd]`` 恰好是使用不超过 ``jumps`` 次跳跃可以覆盖的前缀; * 当前层尚未扫描的位置位于上一层边界之后、``currentEnd`` 以内; * ``nextEnd`` 是已扫描位置再跳一次可以到达的最远下标。 扫描完整层后,所有使用不超过 ``jumps + 1`` 次跳跃的方案,其最后一跳都必然从当前层某个位置出发,因此最远覆盖 位置正是 ``nextEnd``。把它赋给 ``currentEnd`` 后,不变量进入下一层。 当新的 ``currentEnd`` 首次覆盖终点时,已经存在一条使用当前 ``jumps`` 次跳跃的路线。上一层边界尚未覆盖终点, 说明更少跳数不可能到达,所以当前跳数最小。 这也解释了为何不能每次跳到眼前最远的下标。对 ``[2, 3, 0, 1, 4]``,下标 2 虽然是第一跳最远落点,却无法 继续;区间算法会同时扫描下标 1 和 2,并比较它们的 ``index + nums[index]``,因此得到下一层边界 4。 状态演化 ~~~~~~~~ 对 ``[2, 3, 1, 1, 4]``: .. list-table:: :header-rows: 1 * - 扫描下标 - 当前位置最远可达 - ``nextEnd`` - 层结束 - ``jumps`` / ``currentEnd`` * - 0 - 2 - 2 - 是 - ``1 / 2`` * - 1 - 4 - 4 - 否 - ``1 / 2`` * - 2 - 3 - 4 - 是 - ``2 / 4`` 第一次提交后,一跳可覆盖前缀 ``[0, 2]``。扫描下标 1 和 2 后,第二跳可覆盖到下标 4,首次包含终点,答案为 2。 循环边界 ~~~~~~~~ 最后一个下标是目的地,到达后不需要再从它跳出,因此循环只扫描 ``0`` 到 ``n - 2``。若把终点也当作层末提交, 可能额外增加一次跳跃。 单元素数组在进入循环前返回 0。题目保证终点可达,所以在尚未覆盖终点时,每次层结束后的 ``nextEnd`` 都会推进 边界,不需要处理无法前进的失败状态。 代码演进 ~~~~~~~~ ``exhaustiveSearch`` 枚举全部落点,直接表达最少跳数定义,但会重复搜索相同后缀。 ``quadraticDynamicProgramming`` 保存每个下标的最少跳数,把指数级搜索降为多项式时间,但仍逐个更新可达区间。 ``intervalBreadthFirstSearch`` 把相同跳数可达的节点压缩成连续前缀,只维护当前层和下一层的右端点。公开入口采用该 方法,因为它在线性扫描中完成 BFS 分层,并只使用常量状态。 复杂度分析 ~~~~~~~~~~ 设数组长度为 ``n``: * 完整递归最坏为指数时间,递归深度最多 ``O(n)``; * 动态规划最坏 ``O(n^2)`` 时间,使用 ``O(n)`` 额外空间; * 区间 BFS 每个下标只扫描一次,时间 ``O(n)``,额外空间 ``O(1)``。