京公网安备11010502063487号给定一个非负整数数组，你站在下标 0，每个元素表示从这个位置最多能向前跳的步数，保证能到达最后一个位置，求到达末尾的最少跳数。动态规划是 O(n²)：dp[j] 是到达 j 的最少跳数，每个位置更新它能到的所有位置。更好的做法是贪心加"分层"：第 k 跳能到达的所有位置构成第 k 层，扫描的同时记录当前这一层能延伸到的最远位置，走到本层边界时必须再跳一次。本文用真实数据展示一个很有迷惑性的错误贪心，实测线性贪心与动态规划的耗时，给出五种语言的实现，并把分层的过程做成分步演示。
完整题目见官方页面（链接在文末）。基准解是动态规划，O(n²)。所有测试数据保证能到达终点（除最后一个元素外每个元素都不小于 1）。一共 13 组用例，覆盖：官方示例、只有一个元素、两个元素、每次只能走一步、一步就能跳到终点：
输入 [[2,3,1,1,4]] 输出 2 输入 [[2,3,0,1,4]] 输出 2 输入 [[0]] 输出 0 输入 [[1]] 输出 0 输入 [[1,1]] 输出 1 输入 [[2,1]] 输出 1
一个很自然的贪心想法是：每一步都用尽当前位置允许的最大步数，直接跳到最远的那个位置。但"跳得最远"不等于"最少的跳数"：落点位置的元素值可能很小，反而不如落在一个更靠前但元素值大的位置。下面用 20000 个随机数组做了对比：
随机 20000 个数组：每次都跳最大步数的写法与最优解不同的有 2013 个（10.1%）。 最短的一个反例：[2, 3, 1, 3, 2]，每次跳最大步数得到 3 跳，最少只需要 2 跳。
每次都跳最大步数的写法，在约 10% 的随机数组上给出了错误的答案。最短的反例是 [2, 3, 1, 3, 2]：一直跳最大步数，先跳到下标 2（值 1），再到下标 3，再到终点，一共 3 跳；而先跳到下标 1（值 3），一步就能到终点，只需要 2 跳。正确的贪心不是选跳到哪，而是记录"这一层里所有位置能到的最远处"，走到层的边界才决定下一层的边界。
cur_end 是当前这一跳能到达的最远位置（这一层的右边界），farthest 是在这一层里所有位置出发能到达的最远位置。从头扫描到倒数第二个位置：每个位置都更新 farthest；扫描到 cur_end 时说明这一层走完了，必须再跳一次，跳数加一，新的边界是 farthest。不需要扫描最后一个位置，因为到了终点就不用再跳。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): jumps = 0 cur_end = 0 # 当前这一跳能到达的最远位置（这一"层"的右边界） farthest = 0 # 在这一层里所有位置出发，能到达的最远位置 for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) if i == cur_end: # 走到这一层的边界：必须再跳一次，落在 farthest jumps += 1 cur_end = farthest return jumps
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[2,3,1,1,4]] → 2 [[2,3,0,1,4]] → 2 [[0]] → 0 [[1]] → 0 [[1,1]] → 1 [[2,1]] → 1
Java · 解法代码class Solution { public int jump(int[] nums) { int jumps = 0; int curEnd = 0; // 当前这一跳能到达的最远位置（这一"层"的右边界） int farthest = 0; // 在这一层里所有位置出发，能到达的最远位置 for (int i = 0; i < nums.length - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i == curEnd) { // 走到这一层的边界：必须再跳一次，落在 farthest jumps++; curEnd = farthest; } } return jumps; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[2,3,1,1,4]] → 2 [[2,3,0,1,4]] → 2 [[0]] → 0 [[1]] → 0 [[1,1]] → 1 [[2,1]] → 1
Go · 解法代码func jump(nums []int) int { jumps := 0 curEnd := 0 // 当前这一跳能到达的最远位置（这一"层"的右边界） farthest := 0 // 在这一层里所有位置出发，能到达的最远位置 for i := 0; i < len(nums)-1; i++ { if i+nums[i] > farthest { farthest = i + nums[i] } if i == curEnd { // 走到这一层的边界：必须再跳一次，落在 farthest jumps++ curEnd = farthest } } return jumps }
$ go build -o bin . && ./bin < cases.jsonl [[2,3,1,1,4]] → 2 [[2,3,0,1,4]] → 2 [[0]] → 0 [[1]] → 0 [[1,1]] → 1 [[2,1]] → 1
JavaScript · 解法代码function jump(nums) { let jumps = 0; let curEnd = 0; // 当前这一跳能到达的最远位置（这一"层"的右边界） let farthest = 0; // 在这一层里所有位置出发，能到达的最远位置 for (let i = 0; i < nums.length - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i === curEnd) { // 走到这一层的边界：必须再跳一次，落在 farthest jumps++; curEnd = farthest; } } return jumps; }
$ node run.js < cases.jsonl [[2,3,1,1,4]] → 2 [[2,3,0,1,4]] → 2 [[0]] → 0 [[1]] → 0 [[1,1]] → 1 [[2,1]] → 1
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { public: int jump(vector<int>& nums) { int jumps = 0; int curEnd = 0; // 当前这一跳能到达的最远位置（这一"层"的右边界） int farthest = 0; // 在这一层里所有位置出发，能到达的最远位置 for (int i = 0; i < (int)nums.size() - 1; i++) { farthest = max(farthest, i + nums[i]); if (i == curEnd) { // 走到这一层的边界：必须再跳一次，落在 farthest jumps++; curEnd = farthest; } } return jumps; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[2,3,1,1,4]] → 2 [[2,3,0,1,4]] → 2 [[0]] → 0 [[1]] → 0 [[1,1]] → 1 [[2,1]] → 1
共 13 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 13/13 Java 通过 13/13 Go 通过 13/13 JavaScript 通过 13/13 C++ 通过 13/13
数组长度分别为 1000、3000、1 万、3 万，每个元素取 1 到 n/20 的伪随机数（这样动态规划的内层循环要走很多步），每个规模取三次中最快的一次：
数组长度 n（每个元素 1 到 n/20） | 暴力解 | 本文解法
1000 | 1.076 ms | 0.044 ms
3000 | 8.879 ms | 0.135 ms
10000 | 94.964 ms | 0.488 ms
30000 | （未测，太慢） | 1.464 ms动态规划从 1000 到 3000（3 倍）增长约 8.3 倍，从 3000 到 1 万增长约 10.7 倍，符合平方；贪心从 1000 到 3 万（30 倍）增长约 33 倍，是线性。n = 1 万时动态规划 95.0ms，贪心 0.49ms，约 195 倍。动态规划在 n = 3 万时没有再测。
Python 版本另外和动态规划做了随机对拍，数组长度 1 到 12，除最后一个元素外取 1 到 4：
随机对拍 20000 组（长度 1 到 12、除最后一个元素外都不小于 1（保证能到达终点）、取值 1 到 4 的随机数组），solve 与 brute 的结果全部一致。
另外四种语言只在上面 13 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [2, 3, 1, 1, 4]。i = 0 时最远能到 2，同时走到了第 0 层的边界（cur_end = 0），必须再跳一次，跳数变成 1，新的边界是 2；i = 1 时最远能到 4；i = 2 走到边界 2，必须再跳，跳数变成 2，边界变成 4，已经覆盖了终点。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。