1. 项目概述与核心价值

最近在技术社区和求职圈里，“华为OD”和“C卷真题”这几个词的热度一直居高不下。很多朋友，尤其是正在准备机试的Java开发者，都在四处寻找高质量的真题解析和代码实现。今天，我就以一道经典的“跳格子游戏”真题为例，和大家深入聊聊这道题的解题思路、完整的Java代码实现，以及背后那些容易被忽略的细节和优化技巧。这道题在C卷中标注为200分，属于中等偏上难度的题目，非常考验对动态规划或者贪心算法的理解，以及将思路转化为无bug代码的能力。

简单来说，“跳格子游戏”模拟的是一个从起点跳到终点的过程。给你一个非负整数数组，每个位置上的数字代表你从该位置最多可以跳跃的步数。你的目标是从数组的第一个位置（索引0）出发，判断你是否能够到达最后一个位置。这听起来像是一个简单的模拟问题，但其中蕴含的“最优子结构”和“状态转移”思想，是动态规划（DP）和贪心算法的绝佳练兵场。无论是为了应对华为OD机试，还是提升自己的算法思维，吃透这道题都大有裨益。接下来，我将从问题本质拆解开始，逐步推导出两种主流解法，并给出可直接运行的Java代码，最后分享一些我实战中总结的调试心得和避坑指南。

2. 问题深度解析与建模思路

2.1 题目场景还原与抽象

让我们先抛开代码，把问题具象化。想象你面前有一排格子，每个格子里写着一个数字。你站在第一个格子上。格子里的数字告诉你，你从当前格子 最多 能向前跳几格。比如，数组 [2, 3, 1, 1, 4] ，你在索引0（数字2）的位置，那么你既可以跳到索引1，也可以跳到索引2。你的任务是，通过一系列这样的跳跃，最终能否抵达最后一个格子（索引4）。

这里有几个关键约束需要立刻明确：

1. 跳跃力是“最多”值 ：你从位置 i 可以跳到 [i+1, i+nums[i]] 这个区间内的 任意 一个位置，而不是必须跳满 nums[i] 步。这给了我们策略选择的空间。
2. 目标是“能否到达” ：这是一个布尔判断问题（True/False），而不是求最短跳跃次数（那是本题的一个常见变种）。这直接影响了我们算法的设计目标。
3. 数组元素非负 ：这意味着我们永远不会被“负向”跳跃力困住，简化了问题分析。

理解了这些，我们就可以把问题抽象成一个 图论中的可达性问题 ：将每个数组索引视为图的一个节点，从节点 i 到节点 j 存在一条有向边，当且仅当 i < j <= i + nums[i] 。问题就转化为判断从节点0到节点 n-1 是否存在一条路径。

2.2 核心算法思路选型：贪心 vs. 动态规划

面对这个模型，通常有两种主流的算法思路：动态规划（DP）和贪心算法。

动态规划思路 是一种更直观的“自顶向下”或“自底向上”的思考方式。我们定义一个状态 dp[i] ，表示从起点（索引0）能否到达索引 i 。状态转移方程也很自然：对于当前位置 i ，如果我们能到达它（即 dp[i] == true ），那么从 i 出发，所有在它跳跃范围内的位置 j （ i+1 到 i+nums[i] ）也都变得可以到达（即 dp[j] = true ）。我们只需要初始化 dp[0] = true ，然后按顺序更新状态即可。这种方法思路清晰，但时间复杂度为 O(n²)，在最坏情况下（例如数组元素都很大）效率不高。

贪心思路 则更为巧妙和高效。我们不再关心每个具体位置是否可达，而是维护一个关键变量： maxReach ，表示 在当前所有遍历过的位置中，能跳到的最远距离 。我们从左到右遍历数组，对于每一个位置 i ，我们首先判断 i 是否在当前能到达的最远距离 maxReach 之内。如果 i > maxReach ，说明我们根本跳不到 i 这个位置，更别提终点了，可以直接返回 false 。如果 i <= maxReach ，说明我们可以到达 i ，那么我们就用 i + nums[i] 来尝试更新 maxReach 。如果在遍历过程中， maxReach 已经大于等于最后一个索引了，说明终点可达，可以提前返回 true 。这种方法的精髓在于，我们只维护一个最远边界，时间复杂度是 O(n)，空间复杂度是 O(1)，是最优解。

注意 ：贪心算法的正确性需要理解。它之所以有效，是因为问题具有“贪心选择性质”：在可达的范围内，选择任何一个点作为起跳点，其能更新的最远距离 maxReach 只与这个点的值有关，而与如何到达这个点无关。因此，我们只需要一直维护这个最远距离即可。

对于机试场景，我强烈推荐 贪心算法 。理由有三：1) 代码简洁，不易写错；2) 效率最高，能应对大规模数据；3) 充分展示你对问题优化本质的理解。下面，我们就以贪心算法为主线，展开代码实现。

3. 贪心算法代码实现与逐行解读

3.1 基础版本代码实现

我们先给出最简洁、最标准的贪心算法实现。这段代码是解决此题的“黄金模板”。

public class JumpGameGreedy {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int n = nums.length;
        // 初始化最远可达位置
        int maxReach = 0;
        
        // 遍历每一个位置，注意 i 的范围是 [0, n-1)
        for (int i = 0; i < n; i++) {
            // 核心判断：如果当前位置已经超过了之前能跳到的最远位置，则失败
            if (i > maxReach) {
                return false;
            }
            // 更新从当前位置能跳到的最远位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 提前终止：如果最远位置已经能覆盖终点，则成功
            if (maxReach >= n - 1) {
                return true;
            }
        }
        // 循环结束，理论上一定会因为提前返回而结束，这里返回true或false均可，但为逻辑完整，返回maxReach >= n-1的判断
        return maxReach >= n - 1;
    }
}

3.2 代码关键点解析与易错点

1. 边界条件处理 ：开头对输入数组 nums 进行判空是良好的编程习惯。虽然题目通常保证非空，但实际面试或工程中必不可少。

2. 循环条件 i < n ：我们遍历每一个索引。很多人会疑惑，既然 maxReach 可能已经超过 n-1 了，为什么还要遍历？因为我们需要用每个可达的 i 去更新 maxReach 。循环中的 if (i > maxReach) 判断保证了我们只会在可达的范围内进行更新。

3. 核心判断 if (i > maxReach) ：这是贪心算法的灵魂所在。 maxReach 表示的是 在遍历到 i 之前 ，所有位置能帮助我们到达的最远距离。如果当前索引 i 已经超出了这个最远距离，说明我们“力竭”，无法继续前进。例如 nums = [3, 2, 1, 0, 4] ，当 i=4 时， maxReach 在 i=3 处更新后仍然是3（因为 nums[3]=0 ），那么 i=4 > maxReach=3 ，直接返回 false 。

4. 更新 maxReach ： maxReach = Math.max(maxReach, i + nums[i]) 。这里 i + nums[i] 是从当前位置 i 能跳到的最远理论距离。我们始终维护全局最远距离。

5. 提前终止优化 ： if (maxReach >= n - 1) 。这是一个重要的优化。一旦发现最远距离已经能覆盖终点，就没有必要继续遍历后面的元素了，直接返回 true 。这在很多情况下能减少不必要的计算。

6. 循环结束后的返回 ：由于有提前终止的判断，循环内的 return 语句一定会执行。但为了代码逻辑的完整性（比如移除提前终止判断后），在循环外返回 maxReach >= n - 1 是一个更稳健的做法。

4. 动态规划解法对比与实现

虽然贪心是最优解，但动态规划的思路对于理解问题和应对变种题目（如“最少跳跃次数”）非常有帮助。这里也给出一种常见的DP实现，即“自底向上”的递推法。

4.1 DP状态定义与转移方程

我们定义 dp[i] 为布尔值：表示从索引 0 出发，能否到达索引 i 。

• 初始化 ： dp[0] = true ，因为起点肯定是可达的。
• 状态转移 ：对于位置 i （ i 从1到 n-1），我们检查它前面的所有位置 j （ j 从0到 i-1）。如果 j 是可达的（ dp[j] == true ）并且从 j 能一步跳到 i （即 j + nums[j] >= i ），那么 i 就是可达的，设置 dp[i] = true 并跳出对 j 的循环。
• 最终答案 ： dp[n-1] 。

4.2 DP代码实现

public class JumpGameDP {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true; // 起点可达
        
        for (int i = 1; i < n; i++) {
            // 初始化当前i为不可达
            dp[i] = false;
            // 遍历i之前的所有位置j
            for (int j = 0; j < i; j++) {
                // 如果j可达，且从j可以跳到i
                if (dp[j] && (j + nums[j] >= i)) {
                    dp[i] = true;
                    break; // 找到一个可达的j就足够了，跳出内层循环
                }
            }
        }
        return dp[n - 1];
    }
}

4.3 DP与贪心的对比分析

特性	贪心算法	动态规划
时间复杂度	O(n) ，只需一次遍历	O(n²) ，嵌套循环
空间复杂度	O(1) ，只用了几个变量	O(n) ，需要dp数组
代码复杂度	简单，逻辑清晰	相对复杂，涉及状态转移
适用场景	解决“是否可达”的经典最优解	易于理解，是解决“最短跳跃次数”等变种问题的基础
机试推荐	强烈推荐 ，高效且易写	了解即可，不推荐作为首选

从对比可以看出，在华为OD机试这种对效率和正确率都有要求的场景下， 贪心算法是毋庸置疑的首选 。DP解法可以作为你思路的备份，或者向面试官展示你多角度解决问题的能力。

5. 完整可运行测试用例与调试技巧

5.1 构建全面的测试用例

写完代码，验证是关键。以下是我总结的几类必须测试的Case，覆盖了各种边界和特殊情况：

public class TestJumpGame {
    public static void main(String[] args) {
        JumpGameGreedy solution = new JumpGameGreedy();
        
        // 测试用例组
        int[][] testCases = {
            {2, 3, 1, 1, 4}, // 标准可达案例，期望 true
            {3, 2, 1, 0, 4}, // 经典不可达案例（在索引3处值为0），期望 false
            {0},             // 只有一个元素（且为起点和终点），期望 true
            {0, 2, 3},       // 第一步就卡住，期望 false
            {1, 1, 1, 1, 1}, // 每一步都只走1格，但能走到头，期望 true
            {4, 0, 0, 0, 1}, // 第一步就能直接跳到终点附近，期望 true
            {},               // 空数组，期望 false (根据我们的边界处理)
            null,             // null输入，期望 false
            {2, 0, 0},        // 可以跳到索引2，期望 true
            {1, 2, 0, 1},     // 路径：0->1->3，期望 true
        };
        
        boolean[] expected = {true, false, true, false, true, true, false, false, true, true};
        
        for (int i = 0; i < testCases.length; i++) {
            // 处理null用例
            boolean result = (testCases[i] == null) ? solution.canJump(null) : solution.canJump(testCases[i]);
            System.out.printf("测试用例 %d: %s -> 结果: %b, 期望: %b, %s%n",
                    i + 1,
                    testCases[i] == null ? "null" : Arrays.toString(testCases[i]),
                    result,
                    expected[i],
                    result == expected[i] ? "通过" : "失败");
        }
    }
}

5.2 机试环境下的调试心得

在华为OD或其他线上机试平台编程，和你本地IDE开发体验不同。分享几个我踩过坑才总结出的经验：

1. 优先处理边界和异常输入 ：平台测试用例很可能包含空数组 [] 、单元素数组 [0] 等。像我们代码中开头对 nums == null || nums.length == 0 的判断，虽然简单，但能避免很多不必要的 ArrayIndexOutOfBoundsException ，确保代码的健壮性。

2. 善用打印调试（如果允许） ：在不确定逻辑时，可以在关键变量（如 maxReach ）更新后将其打印出来。例如，在循环内加入 System.out.println(“i=” + i + “, maxReach=” + maxReach); 。这能帮你快速定位状态转移是否正确。 注意 ：提交最终代码前务必删除或注释掉所有调试输出。

3. 手动模拟小数据 ：对于像 [3,2,1,0,4] 这样的关键用例，不要依赖大脑空想。在草稿纸或代码注释里，一步步模拟循环：

   • i=0, maxReach=0, i<=maxReach成立，更新maxReach=max(0, 0+3)=3。
   • i=1, maxReach=3, i<=maxReach成立，更新maxReach=max(3, 1+2)=3。
   • i=2, maxReach=3, 成立，更新maxReach=max(3, 2+1)=3。
   • i=3, maxReach=3, 成立，更新maxReach=max(3, 3+0)=3。
   • i=4, maxReach=3, 此时 i=4 > maxReach=3 ，条件触发，返回 false 。 这个过程能极大加深你对算法逻辑的理解，避免想当然。

4. 警惕“差一错误” ：这是算法题最常见的错误之一。在这道题里主要体现在：

   • 循环终止条件：是 i < n 还是 i <= n-1 ？通常使用 i < n 更安全。
   • 索引计算： i + nums[i] 计算的是理论最远 索引 ，不是步数。
   • 终点判断： maxReach >= n - 1 ，因为 n-1 是最后一个元素的索引。

5. 时间复杂度心里有数 ：如果你的代码用了双重循环（DP方法），对于 n=10000 的输入，操作次数可能达到上亿，在有性能要求的平台上很可能超时。这时就要考虑优化为贪心等O(n)算法。

6. 常见问题排查与进阶思考

6.1 你可能遇到的典型错误

1. 错误：将 nums[i] 理解为必须跳的步数。

   • 表现 ：代码逻辑试图精确匹配步数，导致复杂且错误。
   • 修正 ：牢记 nums[i] 是 最大能力 ，你可以跳 1 到 nums[i] 步中的任意步数。

2. 错误：贪心算法中，错误地使用 maxReach 作为循环变量或跳跃目标。

   • 表现 ：写成了 for (int i = 0; i <= maxReach; i++) 然后直接 i += nums[i] ，这混淆了“遍历索引”和“跳跃行为”。
   • 修正 ：严格区分“遍历检查每个位置”和“更新最远距离”两个概念。我们的循环是遍历每个索引 i ，用 i 和 maxReach 的关系来判断当前位置是否可达。

3. 错误：DP解法中，内层循环 j 的遍历顺序或条件错误。

   • 表现 ：从 i-1 往前遍历时，没有及时 break ，或者判断条件写错。
   • 修正 ：确保判断条件是 dp[j] && (j + nums[j] >= i) 。一旦找到这样一个 j ，就应立即设置 dp[i]=true 并跳出循环，避免无谓计算。

6.2 从“能否到达”到“最少步数”

“跳格子游戏”有一个非常经典的变种问题： 求从起点到终点的最少跳跃次数 。这题的解法是贪心算法的进阶应用。

思路是使用“层”的概念。我们维护三个变量： currentEnd （当前跳跃可达范围的边界）、 farthest （在当前范围内能跳到的最远位置）、 jumps （跳跃次数）。遍历数组，当 i 到达 currentEnd 时，意味着你必须进行一次新的跳跃，于是 jumps++ ，并将 currentEnd 更新为 farthest 。代码如下：

public int jump(int[] nums) {
    int n = nums.length;
    int jumps = 0, currentEnd = 0, farthest = 0;
    // 注意，我们只需要遍历到 n-2，因为当 i==n-1 时已经到达终点，无需再跳
    for (int i = 0; i < n - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        // 如果已经可以跳到终点，提前结束
        if (farthest >= n - 1) {
            return jumps + 1;
        }
        // 到达当前跳跃的边界，必须跳一次
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
            // 如果当前边界已经无法推进，说明无法到达终点（针对变种题，原题保证有解则不需要）
            // if (currentEnd <= i) return -1;
        }
    }
    return jumps; // 如果题目保证有解，则一定会提前返回
}

理解这个变种，能让你对贪心算法的“边界”思想有更深刻的把握。

6.3 机试策略与时间分配建议

最后，结合华为OD机试的特点，给几点实战策略：

• 5分钟读题与建模 ：彻底理解题意，像本节开头那样明确约束条件。在草稿纸上画一两个例子。
• 10分钟确定思路与伪代码 ：优先考虑最优解（通常是贪心或常见DP）。写下核心变量和循环结构。
• 15分钟编码 ：将伪代码转化为干净、有良好变量名的Java代码。 立即加上边界处理 。
• 10分钟测试与调试 ：用我们上面列出的几种典型用例测试，特别是 [0] , [3,2,1,0,4] , [1,1,1,1] 。在脑中或纸上进行单步模拟。
• 剩余时间检查 ：检查代码格式、变量名拼写、括号匹配。确保没有死循环或明显性能问题。

这道“跳格子游戏”就像算法学习路上一个精巧的驿站，它用不复杂的场景，串联起了贪心思想、动态规划、边界处理等多个关键知识点。把它吃透，不仅是为了通过某一场考试，更是为了锻炼那种将问题抽象、分解并优雅解决的能力。在平时练习时，不妨多问问自己：为什么贪心在这里有效？DP的状态怎么定义更自然？还有没有其他解法？多进行这样的思考，你的算法功力自然会稳步提升。