1. 项目概述从“跳跃游戏”到算法思维的实战演练最近在整理算法笔记翻到了“跳跃游戏”Jump Game这道题。这题在LeetCode上算是经典中的经典编号55和45一个是判断可行性一个是求最少步数。网上解法很多但很多文章要么只贴个代码要么原理讲得云里雾里对于刚接触贪心或者动态规划的朋友来说看完可能还是不知道怎么想出来的更别提自己写出来了。我当年刷这题也卡了很久后来在一次次调试和琢磨中才把里面的门道摸清楚。今天我就以C/C实现为例不光是给你看源码更想把解题时那个“灵光一现”的思考过程以及代码里每一个变量变化的细节掰开揉碎了讲给你听。无论你是正在备战面试的学生还是想巩固算法基础的开发者相信这篇都能帮你把“跳跃游戏”彻底吃透。简单说“跳跃游戏”模拟的就是你在一个数组上跳格子。数组里的每个数字代表你在那个位置上最多能跳几步。问题一给定一个数组问你一开始在第一个格子能否跳到最后一个格子问题二如果能跳到你最少需要跳几次这听起来像是个游戏但内核是典型的序列决策优化问题是理解贪心算法Greedy Algorithm和动态规划Dynamic Programming, DP思想绝佳的入门案例。我们会先解决判断可行性的问题Jump Game I再攻克最小步数问题Jump Game II最后聊聊这类思想在其它场景比如网络路由、资源分配里的影子。2. 核心思路拆解为什么贪心是“最优解”拿到问题最朴素的想法就是暴力搜索站在起点我有多种跳法每一种跳法又会带来新的多种选择……这俨然一棵决策树。用DFS或BFS当然能解但时间复杂度是指数级的数据量稍大就顶不住。这时就得找规律尝试更优的解法。2.1 Jump Game I聚焦“最远可到达距离”对于问题一能否到达终点关键在于不要纠结于具体跳到哪里而是关注你当前能覆盖的最远范围。我们定义一个变量max_reach表示从起点开始经过若干次跳跃当前能够到达的最远下标。再定义一个变量i表示我们当前遍历到的数组下标。核心逻辑如下从i 0开始遍历数组直到i超过max_reach或遍历结束。在每一个位置i我们更新max_reach max(max_reach, i nums[i])。意思是看看从当前位置i出发能跳到的最远位置i nums[i]是否比历史最远距离max_reach更远。如果在某个时刻max_reach已经大于等于数组最后一个位置的下标n-1说明终点在我们的覆盖范围内游戏成功。反之如果遍历到了一个位置i而这个i已经大于当前的max_reach了说明我们“力竭”了最远只能到max_reach但下一步需要到达的i已经超出了这个范围意味着中间出现了“断层”无法继续前进游戏失败。为什么这是贪心因为我们在每一步遍历每个i时都做出了一个“局部最优”选择总是维护从当前能走到的所有位置中可以跳到的最远距离。我们并没有去模拟具体的跳跃路径比如是先跳2步还是先跳1步而是关心一个全局的、可达的“边界”。这个不断扩张的边界如果能包含终点整体就是可行的。这个思路高效且直观时间复杂度是 O(n)。注意这里最容易混淆的点是i和max_reach的关系。i是我们在“检查”的位置我们必须保证i本身是当前能够走到的即i max_reach才能基于nums[i]去更新最远边界。如果i都走不到后面的计算就无从谈起。2.2 Jump Game II记录“当前边界”与“下次边界”问题二最少跳跃次数在问题一的基础上增加难度。我们依然使用贪心但需要两个关键变量来划分跳跃的“阶段”current_end:当前这一次跳跃所能到达的最远边界。当你开始一次新的跳跃时这个边界就确定了。next_max_reach:在本次跳跃的范围内即i在[0, current_end]所有起跳点所能到达的下一个最远位置。这个值决定了你下一次跳跃的覆盖范围。jumps: 跳跃次数计数器。算法步骤初始化jumps 0,current_end 0,next_max_reach 0。遍历数组最后一个元素不需要遍历因为我们的目标是到达它。对于每个位置i更新next_max_reach max(next_max_reach, i nums[i])。这是在为下一次跳跃积累“弹药”。关键判断如果i走到了current_end说明当前这一次跳跃的潜力已经用尽。此时我们必须发起一次新的跳跃jumps并将新的起跳边界更新为next_max_reach即current_end next_max_reach。如果在更新current_end之前发现next_max_reach已经能覆盖终点了那么再跳一次jumps1就能到达可以提前结束。贪心正确性理解 可以想象成“分层”或“波浪推进”。current_end是当前波浪的锋面在锋面内的所有点我们都不需要增加跳跃次数因为它们属于同一“跳”的覆盖范围。我们在这层波浪里不断寻找能推动下一个波浪最远的点即更新next_max_reach。只有当这层波浪的能量耗尽i current_end我们才不得不发起新的一次跳跃跳到我们预先勘探好的最远位置next_max_reach。这样保证每一次跳跃都尽可能远总体跳跃次数就最少。3. 源码实现与逐行解析理解了思路我们来看C实现。我会提供两个版本的代码清晰注释版和简洁高效版并逐行解释。3.1 Jump Game I 实现#include vector #include algorithm using namespace std; /** * 判断是否能从数组起点跳到终点 (Jump Game I) * param nums 非负整数数组nums[i]表示在位置i最多能跳跃的步数 * return true 如果可以到达最后一个下标否则返回 false */ bool canJump(vectorint nums) { int n nums.size(); if (n 1) return true; // 只有一个元素或空数组默认已在终点 int max_reach 0; // 初始化最远可到达位置为0起点 // 遍历数组但只遍历当前能走到的地方 (i max_reach) for (int i 0; i n i max_reach; i) { // 更新从当前位置i能跳到的最远位置 max_reach max(max_reach, i nums[i]); // 如果最远可到达位置已经覆盖了终点提前返回成功 if (max_reach n - 1) { return true; } } // 循环结束意味着在到达终点前i已经超过了max_reach即遇到了“断层” return false; }关键点解析for循环条件i max_reach是核心保障确保我们只考虑能走到的位置。max_reach max(max_reach, i nums[i])是贪心决策点。提前终止条件if (max_reach n - 1)是一个有效的优化一旦达成目标立即返回。3.2 Jump Game II 实现#include vector #include algorithm using namespace std; /** * 计算到达数组末尾的最少跳跃次数 (Jump Game II) * param nums 非负整数数组 * return 最少跳跃次数 */ int jump(vectorint nums) { int n nums.size(); if (n 1) return 0; // 无需跳跃 int jumps 0; // 跳跃次数 int current_end 0; // 当前跳跃能到达的最远边界 int next_max_reach 0; // 下一次跳跃能到达的最远边界 // 注意只需要遍历到 n-2。因为当 i 到达 n-2 时如果还需要跳最后一次跳跃一定能到 n-1。 for (int i 0; i n - 1; i) { // 不断更新下一次能跳到的最远位置 next_max_reach max(next_max_reach, i nums[i]); // 如果已经走到了当前跳跃的边界 if (i current_end) { jumps; // 不得不进行一次新的跳跃 current_end next_max_reach; // 新的边界是之前探索到的最远位置 // 优化如果新的边界已经能覆盖终点可以提前结束但jumps已加1 if (current_end n - 1) { break; } } } return jumps; }关键点解析for (int i 0; i n - 1; i)这是易错点。我们不需要检查最后一个元素n-1因为我们的目标是到达它。当i走到n-2时如果current_end正好也是n-2那么进入if语句jumpscurrent_end被更新为next_max_reach它至少是n-1循环结束。这正好对应了从n-2起跳的最后一次跳跃。if (i current_end)这是触发跳跃的时机。注意i是遍历索引当它追上“当前边界”时意味着上一跳的所有可能性都已探索完毕必须开启新的一跳。next_max_reach的更新发生在判断i current_end之前这很重要。它保证了我们在当前跳跃的范围内始终在收集下一次跳跃的最远信息。3.3 一个更简洁的Jump Game II写法有些高手会写成下面这样逻辑等价但更紧凑int jump(vectorint nums) { int n nums.size(); int jumps 0, cur_end 0, cur_farthest 0; for (int i 0; i n - 1; i) { cur_farthest max(cur_farthest, i nums[i]); if (i cur_end) { jumps; cur_end cur_farthest; } } return jumps; }这个版本把“提前判断到达终点”的优化去掉了因为当i遍历完n-2后cur_end必然已经更新到至少n-1循环结束jumps也计算完毕。代码更短但理解起来需要多绕一层。我建议初学者先从带注释的清晰版本开始理解。4. 从动态规划视角再审视虽然贪心是本题的最优解但用动态规划DP来思考能帮助我们更好地理解问题结构并且DP是解决更复杂变种问题的基础。4.1 DP状态定义我们可以定义dp[i]为从起点位置0跳到位置i所需的最少跳跃次数。4.2 状态转移方程对于位置i我们如何得到dp[i]呢我们需要查看所有能一步跳到i的位置j即满足j i且j nums[j] i。然后dp[i]就是这些j中对应的dp[j] 1的最小值。用公式表示就是dp[i] min(dp[j] 1), 对于所有满足0 j i且j nums[j] i的j。4.3 DP代码实现用于理解非最优int jumpDP(vectorint nums) { int n nums.size(); vectorint dp(n, INT_MAX); // 初始化为无穷大表示不可达 dp[0] 0; // 起点不需要跳跃 for (int i 1; i n; i) { for (int j 0; j i; j) { // 如果从j可以一步跳到i并且j本身是可达的 if (j nums[j] i dp[j] ! INT_MAX) { dp[i] min(dp[i], dp[j] 1); } } } return dp[n-1] INT_MAX ? -1 : dp[n-1]; // 如果终点不可达返回-1 }这个DP解法的时间复杂度是 O(n²)在数据量大时会超时。但它清晰地揭示了问题的子结构。对比贪心解法 O(n)我们可以看到贪心是如何利用“最远可达”这个性质避免了内层的j循环实现了效率的飞跃。理解DP有助于你明白贪心策略为何有效它本质上是DP的一种优化利用了问题的特殊性质单调性。5. 边界条件、陷阱与调试技巧即使思路清晰实现时也容易踩坑。下面是我在刷题和教学过程中总结的几个常见问题。5.1 关键边界条件空数组或单元素数组这是最简单的边界。如果数组为空或只有一个元素默认已经在“终点”canJump应返回truejump应返回0。代码开头务必处理。起点即为零nums[0] 0且n 1。对于canJump如果起点就是0且后面还有路那显然无法移动应直接返回false。我们的贪心算法能正确处理max_reach初始为0在i0时更新后仍为0循环条件i max_reach在i1时不成立循环结束返回false。数组中包含零这是最容易出错的地方。零意味着“陷阱”在这个点上无法前进。贪心算法的鲁棒性在于只要在到达这个零之前max_reach或next_max_reach能够越过它就不会被卡住。算法关心的是最远边界而不是每个点都必须有前进能力。5.2 常见错误与调试方法错误jump函数返回次数多1或少1。多1通常是因为循环遍历到了最后一个元素n-1并在那里错误地增加了一次跳跃。记住我们的跳跃动作发生在i current_end时而current_end的更新是基于i在[0, current_end]范围内计算出的next_max_reach。当i为n-1时我们已经到达终点不应再跳。所以循环条件应为i n - 1。少1通常发生在终点刚好是某次跳跃的边界时。例如数组[2, 3, 1, 1, 4]。正确的跳跃路径是 0-1-4跳2次。在i1时current_end是1从0跳1步到1的边界i current_end触发跳跃jumps变为1current_end更新为next_max_reach即从位置1跳3步能到的位置4。此时current_end (4) n-1 (4)循环可以提前终止jumps1看起来少了不因为从位置1到位置4的这次跳跃已经包含在jumps里了。最终返回1等等我们总共跳了两次啊这里就是理解的关键jumps变量记录的是“已经完成的跳跃次数”。初始为0在起点0我们还没有跳。当i走到current_end(0)时我们发起第一次跳跃0-?jumps变为1。这次跳跃的落点范围是[1, next_max_reach]。当i走到新的current_end假设是1时我们发起第二次跳跃jumps变为2。所以jumps的最终值就是总跳跃次数。对于[2,3,1,1,4]模拟过程如下表inums[i]cur_endnext_maxicur_end?jumps动作解释020max(0, 02)2是 (00)0-1第一次跳跃从0起跳最远能到2。更新cur_end2132max(2, 13)4否 (1!2)1在第一次跳跃的覆盖范围内移动并探索到下次能跳到4212max(4, 21)4是 (22)1-2第二次跳跃第一次跳跃的潜力用尽从当前范围位置1或2起跳最远能到4。更新cur_end4314max(4, 31)4否 (3!4)2在第二次跳跃的覆盖范围内移动已覆盖终点循环结束最终jumps2正确。通过制作这样的表格是调试贪心算法最直观的方法。错误canJump函数漏判。确保你的max_reach更新公式是max(max_reach, i nums[i])而不是max_reach nums[i]。后者是错误的它变成了从之前的最远点连续跳而不是从每个可达点尝试跳。确保循环条件包含i max_reach。如果写成i n当遇到[0, 2, 3]这样的数组时会在i1时继续计算而实际上i1是走不到的会导致错误更新或访问越界。5.3 测试用例设计自己编写测试用例是保证代码正确的关键。应该覆盖以下场景常规用例[2,3,1,1,4](true, 2),[3,2,1,0,4](false, N/A)边界用例[],[0],[1],[0, 1],[1, 0, 1]包含零的用例[2, 0, 0, 1, 4](false),[2, 0, 2, 0, 1](true, 3)一步到位用例[5, 0, 0, 0, 0](true, 1)大数用例验证不会溢出i nums[i]可能超过int范围题目通常保证不会但思考一下是好的习惯。6. 算法扩展与实战联想掌握了基础版本我们可以看看它的变种和一些实际应用场景这能帮你更好地内化这种“贪心边界扩展”的思想。6.1 变种问题举例跳跃游戏 III给定数组和起点索引你只能跳到i arr[i]或i - arr[i]的位置问是否能跳到任意一个值为0的元素。这不再是贪心通常用BFS或DFS来搜索路径。跳跃游戏 IV给你一个整数数组arr一开始你在下标0处。你可以跳到下标i 1、i - 1或者j其中arr[i] arr[j]且i ! j。求到达最后一个下标的最少操作次数。这需要将问题转化为图的最短路径使用BFS求解。带权值的最小跳跃次数如果每次跳跃消耗的体力与跳跃距离相关求消耗最小体力的跳法。这就变成了一个最短路径问题可以用Dijkstra算法。6.2 实际应用场景联想这种“在可及范围内寻找最优下一步”的思想在很多领域都有体现网络路由路由器根据当前网络状态跳数、带宽、延迟选择下一跳。它不一定知道全局最优路径但会在已知的邻居中选择一个看起来最好的类似贪心协议如RIP。资源分配与调度例如在有限的时间内完成多项任务每次选择当前能做的、收益最高或耗时最短的任务。游戏AI中的移动在部分信息或实时性要求高的游戏中AI可能不会计算到终点的完整路径而是每帧根据周围环境障碍、敌人决定一个最佳的移动方向或目标点。股票买卖系列问题有些股票问题如买卖股票的最佳时机II中“今天买明天卖”的贪心策略也蕴含着在每一个上升波段都获利的局部最优思想。“跳跃游戏”虽然简单但它像一把钥匙打开了贪心算法和优化问题的一扇门。它的核心——维护一个当前最优的边界并利用这个边界做决策——是一种非常有力的思维模式。下次当你遇到类似“在限制条件下寻找最优序列”的问题时不妨想想能不能也定义一个“最远可到达”或者“当前最佳”的状态用贪心去逼近答案。当然也要时刻警惕贪心不是万能的证明其正确性往往是解题中最关键也最困难的一步。对于跳跃游戏我们通过“最远距离”的单调不减性证明了贪心选择可以得到全局最优解。多练习多思考这种算法直觉会慢慢成为你的一部分。
贪心算法实战：从跳跃游戏到序列决策优化，详解C++实现与边界处理
发布时间：2026/7/27 5:58:02
1. 项目概述从“跳跃游戏”到算法思维的实战演练最近在整理算法笔记翻到了“跳跃游戏”Jump Game这道题。这题在LeetCode上算是经典中的经典编号55和45一个是判断可行性一个是求最少步数。网上解法很多但很多文章要么只贴个代码要么原理讲得云里雾里对于刚接触贪心或者动态规划的朋友来说看完可能还是不知道怎么想出来的更别提自己写出来了。我当年刷这题也卡了很久后来在一次次调试和琢磨中才把里面的门道摸清楚。今天我就以C/C实现为例不光是给你看源码更想把解题时那个“灵光一现”的思考过程以及代码里每一个变量变化的细节掰开揉碎了讲给你听。无论你是正在备战面试的学生还是想巩固算法基础的开发者相信这篇都能帮你把“跳跃游戏”彻底吃透。简单说“跳跃游戏”模拟的就是你在一个数组上跳格子。数组里的每个数字代表你在那个位置上最多能跳几步。问题一给定一个数组问你一开始在第一个格子能否跳到最后一个格子问题二如果能跳到你最少需要跳几次这听起来像是个游戏但内核是典型的序列决策优化问题是理解贪心算法Greedy Algorithm和动态规划Dynamic Programming, DP思想绝佳的入门案例。我们会先解决判断可行性的问题Jump Game I再攻克最小步数问题Jump Game II最后聊聊这类思想在其它场景比如网络路由、资源分配里的影子。2. 核心思路拆解为什么贪心是“最优解”拿到问题最朴素的想法就是暴力搜索站在起点我有多种跳法每一种跳法又会带来新的多种选择……这俨然一棵决策树。用DFS或BFS当然能解但时间复杂度是指数级的数据量稍大就顶不住。这时就得找规律尝试更优的解法。2.1 Jump Game I聚焦“最远可到达距离”对于问题一能否到达终点关键在于不要纠结于具体跳到哪里而是关注你当前能覆盖的最远范围。我们定义一个变量max_reach表示从起点开始经过若干次跳跃当前能够到达的最远下标。再定义一个变量i表示我们当前遍历到的数组下标。核心逻辑如下从i 0开始遍历数组直到i超过max_reach或遍历结束。在每一个位置i我们更新max_reach max(max_reach, i nums[i])。意思是看看从当前位置i出发能跳到的最远位置i nums[i]是否比历史最远距离max_reach更远。如果在某个时刻max_reach已经大于等于数组最后一个位置的下标n-1说明终点在我们的覆盖范围内游戏成功。反之如果遍历到了一个位置i而这个i已经大于当前的max_reach了说明我们“力竭”了最远只能到max_reach但下一步需要到达的i已经超出了这个范围意味着中间出现了“断层”无法继续前进游戏失败。为什么这是贪心因为我们在每一步遍历每个i时都做出了一个“局部最优”选择总是维护从当前能走到的所有位置中可以跳到的最远距离。我们并没有去模拟具体的跳跃路径比如是先跳2步还是先跳1步而是关心一个全局的、可达的“边界”。这个不断扩张的边界如果能包含终点整体就是可行的。这个思路高效且直观时间复杂度是 O(n)。注意这里最容易混淆的点是i和max_reach的关系。i是我们在“检查”的位置我们必须保证i本身是当前能够走到的即i max_reach才能基于nums[i]去更新最远边界。如果i都走不到后面的计算就无从谈起。2.2 Jump Game II记录“当前边界”与“下次边界”问题二最少跳跃次数在问题一的基础上增加难度。我们依然使用贪心但需要两个关键变量来划分跳跃的“阶段”current_end:当前这一次跳跃所能到达的最远边界。当你开始一次新的跳跃时这个边界就确定了。next_max_reach:在本次跳跃的范围内即i在[0, current_end]所有起跳点所能到达的下一个最远位置。这个值决定了你下一次跳跃的覆盖范围。jumps: 跳跃次数计数器。算法步骤初始化jumps 0,current_end 0,next_max_reach 0。遍历数组最后一个元素不需要遍历因为我们的目标是到达它。对于每个位置i更新next_max_reach max(next_max_reach, i nums[i])。这是在为下一次跳跃积累“弹药”。关键判断如果i走到了current_end说明当前这一次跳跃的潜力已经用尽。此时我们必须发起一次新的跳跃jumps并将新的起跳边界更新为next_max_reach即current_end next_max_reach。如果在更新current_end之前发现next_max_reach已经能覆盖终点了那么再跳一次jumps1就能到达可以提前结束。贪心正确性理解 可以想象成“分层”或“波浪推进”。current_end是当前波浪的锋面在锋面内的所有点我们都不需要增加跳跃次数因为它们属于同一“跳”的覆盖范围。我们在这层波浪里不断寻找能推动下一个波浪最远的点即更新next_max_reach。只有当这层波浪的能量耗尽i current_end我们才不得不发起新的一次跳跃跳到我们预先勘探好的最远位置next_max_reach。这样保证每一次跳跃都尽可能远总体跳跃次数就最少。3. 源码实现与逐行解析理解了思路我们来看C实现。我会提供两个版本的代码清晰注释版和简洁高效版并逐行解释。3.1 Jump Game I 实现#include vector #include algorithm using namespace std; /** * 判断是否能从数组起点跳到终点 (Jump Game I) * param nums 非负整数数组nums[i]表示在位置i最多能跳跃的步数 * return true 如果可以到达最后一个下标否则返回 false */ bool canJump(vectorint nums) { int n nums.size(); if (n 1) return true; // 只有一个元素或空数组默认已在终点 int max_reach 0; // 初始化最远可到达位置为0起点 // 遍历数组但只遍历当前能走到的地方 (i max_reach) for (int i 0; i n i max_reach; i) { // 更新从当前位置i能跳到的最远位置 max_reach max(max_reach, i nums[i]); // 如果最远可到达位置已经覆盖了终点提前返回成功 if (max_reach n - 1) { return true; } } // 循环结束意味着在到达终点前i已经超过了max_reach即遇到了“断层” return false; }关键点解析for循环条件i max_reach是核心保障确保我们只考虑能走到的位置。max_reach max(max_reach, i nums[i])是贪心决策点。提前终止条件if (max_reach n - 1)是一个有效的优化一旦达成目标立即返回。3.2 Jump Game II 实现#include vector #include algorithm using namespace std; /** * 计算到达数组末尾的最少跳跃次数 (Jump Game II) * param nums 非负整数数组 * return 最少跳跃次数 */ int jump(vectorint nums) { int n nums.size(); if (n 1) return 0; // 无需跳跃 int jumps 0; // 跳跃次数 int current_end 0; // 当前跳跃能到达的最远边界 int next_max_reach 0; // 下一次跳跃能到达的最远边界 // 注意只需要遍历到 n-2。因为当 i 到达 n-2 时如果还需要跳最后一次跳跃一定能到 n-1。 for (int i 0; i n - 1; i) { // 不断更新下一次能跳到的最远位置 next_max_reach max(next_max_reach, i nums[i]); // 如果已经走到了当前跳跃的边界 if (i current_end) { jumps; // 不得不进行一次新的跳跃 current_end next_max_reach; // 新的边界是之前探索到的最远位置 // 优化如果新的边界已经能覆盖终点可以提前结束但jumps已加1 if (current_end n - 1) { break; } } } return jumps; }关键点解析for (int i 0; i n - 1; i)这是易错点。我们不需要检查最后一个元素n-1因为我们的目标是到达它。当i走到n-2时如果current_end正好也是n-2那么进入if语句jumpscurrent_end被更新为next_max_reach它至少是n-1循环结束。这正好对应了从n-2起跳的最后一次跳跃。if (i current_end)这是触发跳跃的时机。注意i是遍历索引当它追上“当前边界”时意味着上一跳的所有可能性都已探索完毕必须开启新的一跳。next_max_reach的更新发生在判断i current_end之前这很重要。它保证了我们在当前跳跃的范围内始终在收集下一次跳跃的最远信息。3.3 一个更简洁的Jump Game II写法有些高手会写成下面这样逻辑等价但更紧凑int jump(vectorint nums) { int n nums.size(); int jumps 0, cur_end 0, cur_farthest 0; for (int i 0; i n - 1; i) { cur_farthest max(cur_farthest, i nums[i]); if (i cur_end) { jumps; cur_end cur_farthest; } } return jumps; }这个版本把“提前判断到达终点”的优化去掉了因为当i遍历完n-2后cur_end必然已经更新到至少n-1循环结束jumps也计算完毕。代码更短但理解起来需要多绕一层。我建议初学者先从带注释的清晰版本开始理解。4. 从动态规划视角再审视虽然贪心是本题的最优解但用动态规划DP来思考能帮助我们更好地理解问题结构并且DP是解决更复杂变种问题的基础。4.1 DP状态定义我们可以定义dp[i]为从起点位置0跳到位置i所需的最少跳跃次数。4.2 状态转移方程对于位置i我们如何得到dp[i]呢我们需要查看所有能一步跳到i的位置j即满足j i且j nums[j] i。然后dp[i]就是这些j中对应的dp[j] 1的最小值。用公式表示就是dp[i] min(dp[j] 1), 对于所有满足0 j i且j nums[j] i的j。4.3 DP代码实现用于理解非最优int jumpDP(vectorint nums) { int n nums.size(); vectorint dp(n, INT_MAX); // 初始化为无穷大表示不可达 dp[0] 0; // 起点不需要跳跃 for (int i 1; i n; i) { for (int j 0; j i; j) { // 如果从j可以一步跳到i并且j本身是可达的 if (j nums[j] i dp[j] ! INT_MAX) { dp[i] min(dp[i], dp[j] 1); } } } return dp[n-1] INT_MAX ? -1 : dp[n-1]; // 如果终点不可达返回-1 }这个DP解法的时间复杂度是 O(n²)在数据量大时会超时。但它清晰地揭示了问题的子结构。对比贪心解法 O(n)我们可以看到贪心是如何利用“最远可达”这个性质避免了内层的j循环实现了效率的飞跃。理解DP有助于你明白贪心策略为何有效它本质上是DP的一种优化利用了问题的特殊性质单调性。5. 边界条件、陷阱与调试技巧即使思路清晰实现时也容易踩坑。下面是我在刷题和教学过程中总结的几个常见问题。5.1 关键边界条件空数组或单元素数组这是最简单的边界。如果数组为空或只有一个元素默认已经在“终点”canJump应返回truejump应返回0。代码开头务必处理。起点即为零nums[0] 0且n 1。对于canJump如果起点就是0且后面还有路那显然无法移动应直接返回false。我们的贪心算法能正确处理max_reach初始为0在i0时更新后仍为0循环条件i max_reach在i1时不成立循环结束返回false。数组中包含零这是最容易出错的地方。零意味着“陷阱”在这个点上无法前进。贪心算法的鲁棒性在于只要在到达这个零之前max_reach或next_max_reach能够越过它就不会被卡住。算法关心的是最远边界而不是每个点都必须有前进能力。5.2 常见错误与调试方法错误jump函数返回次数多1或少1。多1通常是因为循环遍历到了最后一个元素n-1并在那里错误地增加了一次跳跃。记住我们的跳跃动作发生在i current_end时而current_end的更新是基于i在[0, current_end]范围内计算出的next_max_reach。当i为n-1时我们已经到达终点不应再跳。所以循环条件应为i n - 1。少1通常发生在终点刚好是某次跳跃的边界时。例如数组[2, 3, 1, 1, 4]。正确的跳跃路径是 0-1-4跳2次。在i1时current_end是1从0跳1步到1的边界i current_end触发跳跃jumps变为1current_end更新为next_max_reach即从位置1跳3步能到的位置4。此时current_end (4) n-1 (4)循环可以提前终止jumps1看起来少了不因为从位置1到位置4的这次跳跃已经包含在jumps里了。最终返回1等等我们总共跳了两次啊这里就是理解的关键jumps变量记录的是“已经完成的跳跃次数”。初始为0在起点0我们还没有跳。当i走到current_end(0)时我们发起第一次跳跃0-?jumps变为1。这次跳跃的落点范围是[1, next_max_reach]。当i走到新的current_end假设是1时我们发起第二次跳跃jumps变为2。所以jumps的最终值就是总跳跃次数。对于[2,3,1,1,4]模拟过程如下表inums[i]cur_endnext_maxicur_end?jumps动作解释020max(0, 02)2是 (00)0-1第一次跳跃从0起跳最远能到2。更新cur_end2132max(2, 13)4否 (1!2)1在第一次跳跃的覆盖范围内移动并探索到下次能跳到4212max(4, 21)4是 (22)1-2第二次跳跃第一次跳跃的潜力用尽从当前范围位置1或2起跳最远能到4。更新cur_end4314max(4, 31)4否 (3!4)2在第二次跳跃的覆盖范围内移动已覆盖终点循环结束最终jumps2正确。通过制作这样的表格是调试贪心算法最直观的方法。错误canJump函数漏判。确保你的max_reach更新公式是max(max_reach, i nums[i])而不是max_reach nums[i]。后者是错误的它变成了从之前的最远点连续跳而不是从每个可达点尝试跳。确保循环条件包含i max_reach。如果写成i n当遇到[0, 2, 3]这样的数组时会在i1时继续计算而实际上i1是走不到的会导致错误更新或访问越界。5.3 测试用例设计自己编写测试用例是保证代码正确的关键。应该覆盖以下场景常规用例[2,3,1,1,4](true, 2),[3,2,1,0,4](false, N/A)边界用例[],[0],[1],[0, 1],[1, 0, 1]包含零的用例[2, 0, 0, 1, 4](false),[2, 0, 2, 0, 1](true, 3)一步到位用例[5, 0, 0, 0, 0](true, 1)大数用例验证不会溢出i nums[i]可能超过int范围题目通常保证不会但思考一下是好的习惯。6. 算法扩展与实战联想掌握了基础版本我们可以看看它的变种和一些实际应用场景这能帮你更好地内化这种“贪心边界扩展”的思想。6.1 变种问题举例跳跃游戏 III给定数组和起点索引你只能跳到i arr[i]或i - arr[i]的位置问是否能跳到任意一个值为0的元素。这不再是贪心通常用BFS或DFS来搜索路径。跳跃游戏 IV给你一个整数数组arr一开始你在下标0处。你可以跳到下标i 1、i - 1或者j其中arr[i] arr[j]且i ! j。求到达最后一个下标的最少操作次数。这需要将问题转化为图的最短路径使用BFS求解。带权值的最小跳跃次数如果每次跳跃消耗的体力与跳跃距离相关求消耗最小体力的跳法。这就变成了一个最短路径问题可以用Dijkstra算法。6.2 实际应用场景联想这种“在可及范围内寻找最优下一步”的思想在很多领域都有体现网络路由路由器根据当前网络状态跳数、带宽、延迟选择下一跳。它不一定知道全局最优路径但会在已知的邻居中选择一个看起来最好的类似贪心协议如RIP。资源分配与调度例如在有限的时间内完成多项任务每次选择当前能做的、收益最高或耗时最短的任务。游戏AI中的移动在部分信息或实时性要求高的游戏中AI可能不会计算到终点的完整路径而是每帧根据周围环境障碍、敌人决定一个最佳的移动方向或目标点。股票买卖系列问题有些股票问题如买卖股票的最佳时机II中“今天买明天卖”的贪心策略也蕴含着在每一个上升波段都获利的局部最优思想。“跳跃游戏”虽然简单但它像一把钥匙打开了贪心算法和优化问题的一扇门。它的核心——维护一个当前最优的边界并利用这个边界做决策——是一种非常有力的思维模式。下次当你遇到类似“在限制条件下寻找最优序列”的问题时不妨想想能不能也定义一个“最远可到达”或者“当前最佳”的状态用贪心去逼近答案。当然也要时刻警惕贪心不是万能的证明其正确性往往是解题中最关键也最困难的一步。对于跳跃游戏我们通过“最远距离”的单调不减性证明了贪心选择可以得到全局最优解。多练习多思考这种算法直觉会慢慢成为你的一部分。
