前阵子在一家在线刷题平台上碰到一道困难题，题号 1340，名字叫 Jump Game V。说真的，第一次读完题目，我完全没搞清楚它和普通跳跃游戏有什么联系。题目标签写着动态规划，可如果直接套经典跳跃问题的思路，会掉进贪心的坑里。我前前后后写了三版，最后把运行时间压到了 97ms，才算是真正把这道题吃透。这篇文章就把完整的思考过程、实现细节和踩过的坑都写出来，适合刚开始刷困难题、想在动态规划上找手感的人，也适合已经能通过、但想知道为什么按高度排序能这么快的朋友。
先给结论：这道题不是让我们判断能不能跳到终点，而是给定一堆柱子，人只能从高处往低处跳，问从任意柱子出发，最多能踩到几根柱子。因为存在“只能从高到低”这个限制，所有跳跃关系天然无环，所以它本质上是在一张有向无环图上求最长路径。有了这个视角，后续的解法就顺了。
1. 先把题目翻译成人话
1.1 跳跃规则到底在限制什么
不考虑程序语言，先拿现实场景类比。某块地面上有一排柱子，每根柱子有不同的高度，你站在某根柱子上，每次可以向左或向右跳，最远跳 d 步。但有个硬性要求：你只能跳到严格低于当前柱子的位置，而且从当前位置到目标位置之间经过的所有柱子，都必须比当前柱子矮。如果中间出现一根比当前柱子高或等高的柱子，就会被挡住，不能再往前越过去。
比如数组是[6, 4, 14, 6, 8]，d = 2。站在下标 0，高度 6，向右看：下标 1 高度 4，满足条件，可以跳；下标 2 高度 14，比 6 高，不能跳。如果d = 3，想从下标 0 跳到下标 3，中间要经过下标 1 的 4 和下标 2 的 14，14 比 6 高，所以这堵墙挡住了整条路，不能跳。注意下标 3 本身高度也是 6，和起点相等，也不满足“严格低于当前柱子”的条件。
所以这个限制有两个层次：第一层是距离限制，abs(i - j) <= d；第二层是路径限制，i和j之间的所有位置都必须满足arr[k] < arr[i]。很多人只注意到第一层，忽略了第二层。第二层才是这个题真正 tricky 的地方。
为什么要强调“严格低于”？因为高度相等时，彼此之间没有合法边。如果数组中所有柱子高度都相同，那答案必然是 1，因为任何一跳都不满足条件。这个小细节会直接影响后面的边界判断。
1.2 把问题变成一张有向无环图
如果把每一步跳跃都看成一条有向边，边的方向一定是从较高的柱子指向较低的柱子。也就是说，如果存在i -> j，一定有arr[j] < arr[i]。高度关系给所有边规定了一个方向：永远从高往低走，不可能出现从低到高的边，更不可能出现环路。
于是问题就变清晰了：在一张有向无环图 DAG 上，从任意节点出发，求最长路径的节点数量。注意不是最长边数，是节点数，起点也算一个，所以最终结果要加 1。
DAG 上的最长路径是可以用动态规划解决的，而且有明确的递推方向。一般图上的最长路径是 NP 难问题，但 DAG 不是。这个区别非常关键，它决定了我们不能用贪心，但也不需要暴力搜索所有路径。
2. 思路演进：为什么最终选按高度排序的 DP
2.1 第一反应：暴力 DFS 为什么不行
看到“从任意点出发求最长”，第一反应往往是 DFS。从每个点出发，枚举所有可以跳到的点，递归下去，记录最大值。这个思路正确，但问题有两个：一是重复计算严重，同一个节点会被不同起点反复搜索；二是递归深度可能达到数组长度，在数据范围比较大的时候有爆栈风险。
可以用记忆化搜索优化，memo[i]记录从i出发的答案，这样每个节点只算一次。理论上复杂度可以接受。但我个人在实际提交中发现，递归版的常数比较大，而且unordered_map做记忆化比普通数组慢不少。如果评测环境对运行时间比较敏感，很容易落在超时边缘。那时候我就想，能不能用迭代 DP 把所有递归都干掉。
2.2 状态定义和计算顺序才是核心
设dp[i]表示从下标i出发最多能访问的柱子数量。如果i能合法跳到j，那么可以得到转移：
dp[i] = max(dp[i], dp[j] + 1)
这个转移本身简单到让人怀疑人生：难点不在方程，而在计算顺序。因为dp[i]依赖dp[j]，而dp[j]对应的高度必须严格低于arr[i]。如果我们只是从左到右遍历下标，dp[j]可能还没被算出来。
举个例子，arr = [1, 5, 3]，如果从左到右算：先算下标 0，dp[0] = 1；再算下标 1，发现可以跳到下标 2，但下标 2 还没算，就没法更新dp[1]。所以要找到一个顺序，让所有比i低的节点都排在i前面。
最自然的顺序就是高度升序。把下标按照数组值从小到大排序，然后依次处理。因为所有arr[j] < arr[i]的j，都会比i更早被处理，dp[j]就已经是最终值。这时候dp[i]的转移就完全没有依赖问题了。
这就是整个题目的核心钥匙：高度本身就是拓扑序。我们不需要写递归，不需要记忆化，只需要用一个排序把计算顺序固定住。
2.3 同高度节点如何处理
排序的时候，如果两个位置高度相同，它们之间是不能跳跃的。所以谁排在前面其实无所谓。但为了排序的稳定性，我会在高度相同时按下标排序，这样行为可预测，也避免某些奇怪的不确定因素。严格来说不会影响答案，因为同高度之间没有转移边。
3. 97ms 版本实现拆解
3.1 完整代码先放出来
我用 C++ 写，代码如下：
class Solution { public: int maxJumps(vector<int>& arr, int d) { int n = arr.size(); vector<int> idx(n); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int a, int b) { if (arr[a] != arr[b]) return arr[a] < arr[b]; return a < b; }); vector<int> dp(n, 1); int ans = 1; for (int i : idx) { // 向左扩展 for (int j = i - 1; j >= 0 && j >= i - d; --j) { if (arr[j] >= arr[i]) break; dp[i] = max(dp[i], dp[j] + 1); } // 向右扩展 for (int j = i + 1; j < n && j <= i + d; ++j) { if (arr[j] >= arr[i]) break; dp[i] = max(dp[i], dp[j] + 1); } ans = max(ans, dp[i]); } return ans; } };整个代码不到 30 行，核心逻辑就是两个循环加一个排序。看起来简单，但每一行都有讲究。
3.2 关键细节：为什么遇到墙就 break
向左扩展的循环从i - 1开始，一直扫到i - d边界。每扫到一个位置j，如果arr[j] >= arr[i]，直接break；否则就用dp[j] + 1更新dp[i]。
break而不是continue，这是最容易写错的地方。因为跳跃要求路径上的所有中间位置都必须低于起点。如果从i向左看，发现离i最近的那个位置已经不比i低了，那再往左的位置一定被这个“高墙”挡住，绝对不可能从i合法跳过去。继续扫下去没有意义，必须停。continue会让循环继续扫描，误以为能越过墙，结果就是答案偏大。
同理向右也是break。这个语义和“一段连续区间内所有点都小于当前值”完全一致：只要区间起点处不满足，整个区间就都不满足。
3.3 为什么 dp[j] 一定已经算好
这一点是理解这个解法的关键。我们先把idx按高度升序排好，然后按这个顺序处理。当处理到下标i时，数组里所有比它矮的下标都已经在它之前被处理过了。能作为合法跳跃目标的j，必须满足arr[j] < arr[i]，所以j肯定已经处理完，dp[j]是一个确定值。
换句话说，高度升序就是这张 DAG 的拓扑序。每个节点的所有前驱都在它前面，所以可以放心地做状态转移。这也是我来回改版后最想强调的一点：这道题不是转移方程难，而是大多数人会忽略计算顺序。
3.4 手推一个简单用例
我们用arr = [5, 3, 4, 2]，d = 2来走一遍。
高度排序后的处理顺序是：下标 3（值 2）、下标 1（值 3）、下标 2（值 4）、下标 0（值 5）。
- 处理下标 3：左右都没有可跳点，
dp[3] = 1 - 处理下标 1：向左看下标 0，值 5 大于 3，停；向右看下标 2，值 4 大于 3，停。
dp[1] = 1 - 处理下标 2：向左看下标 1，值 3 小于 4，
dp[2] = max(1, dp[1] + 1) = 2；继续向左下标 0，值 5 大于 4，停。向右看下标 3，值 2 小于 4，dp[2] = max(2, dp[3] + 1) = 2。所以dp[2] = 2 - 处理下标 0：向右看下标 1，值 3 小于 5，
dp[0] = dp[1] + 1 = 2；继续下标 2，值 4 小于 5，dp[0] = max(2, dp[2] + 1) = 3；再继续下标 3，已经超出i + d = 2，循环结束。所以dp[0] = 3
最终答案ans = 3。对应的路径是0 -> 2 -> 1：从高度 5 跳到高度 4，再跳到高度 3，中间所有柱子都低于起点。这个手推过程能看出来，左扩展右扩展其实就是在枚举所有合法跳跃目标，而排序保证了目标点都处于已计算状态。
3.5 复杂度和边界情况
排序是O(n log n)，内层两个循环每个点最多扫描2d个位置，所以总复杂度O(n log n + n*d)，空间复杂度O(n)。题目给出的数据量通常是n <= 1000，这个复杂度完全足够。
边界情况要注意几个：
n == 1：只能访问自己，返回 1。- 所有高度相同：任意两点之间都不满足严格小于，每个
dp都为 1，答案 1。 - 数组严格递增：只有从高处往低处跳，所以最长路径通常是 1，因为末尾最高可以往前跳，但前面低点没法往后跳，需要排序 DP 才能正确处理。
d很大，超过数组长度：循环范围会被j >= 0和j < n截断，不会越界。
4. 从超时到 97ms 的调试实录
4.1 第一版为什么慢
我第一版用的是递归记忆化，用unordered_map<int, int>做 memo，写起来倒是顺手，但跑出来的结果让我非常难受。递归函数本身有额外开销，哈希表在访问时也有常量消耗。更关键的是，我在枚举可跳点时每次都会重新计算“从 i 到 j 中间所有点是否都小于 arr[i]”，这个验证过程写得很啰嗦，性能自然上不去。后来改用排序递推，不仅快，而且代码更短，逻辑也更直白。
如果你自己写递归版本，其实也能过，不一定会超时。但如果追求稳定低耗时，我会更推荐迭代 DP。递归不是不好，而是这个题的递推顺序天然明确，用迭代可以完全避免函数调用栈和哈希表的问题。
4.2 我踩过的三个坑
第一个坑：不排序直接从左到右算。这样会因为dp[j]还没算出来而漏掉很多答案。尤其是向右跳的情况，目标点下标可能比当前点大，恰好不在已计算区间内。我一度在测试用例上得到奇怪的偏小结果，排查半天才意识到是顺序问题。
第二个坑：把break写成continue。这个错误非常隐蔽，因为在小数组上可能侥幸通过，但一旦出现“先低后高再低”的形状，continue会让程序越过中间的墙，错误地认为可以跳到更远的低点，答案偏大。记住，遇到大于等于当前高度的点必须立即停止扩展。
第三个坑：判断条件写成了arr[j] > arr[i]，把等于的情况漏掉了。题目要求严格低于，所以高度相等也是墙。数组里如果有大量相同的值，这个错误会导致答案异常偏大。必须写>=。
4.3 从 97ms 这个数字能读出什么
97ms 只是一个实测值，不同环境浮动很正常。它说明这套实现没有明显拖后腿的地方：没有递归，没有哈希表，没有不必要的对象拷贝，排序也是标准库的快速排序。
如果想让代码再快一点点，可以考虑几个小点：d和n存成局部变量；循环里避免反复调用arr.size()；排序 lambda 里直接引用外部数组，不要拷贝。但这些属于常量级别优化，改变不了复杂度。我觉得为了几毫秒牺牲代码可读性不太划算，所以在最终代码里保留了清晰的结构。
4.4 一条独家调试建议
这类题建议用随机暴力和优化 DP 对拍。小范围数据上，写一个最朴素的 DFS 暴力版本，再去和优化版本跑同一组随机数组，几十组之后大概率能找出边界条件问题。我处理高度相等和“墙”这两个坑时，就是靠对拍找到的。别直接盯着大样例死磕，很难看出问题。
5. 从这道题延伸出的通用思考
5.1 这不是经典跳跃游戏
经典跳跃游戏问的是“能不能到达最后一个位置”，通常用贪心维护最远可达位置就行。但这题问的是“任意起点到任意目标的最长路径”，没有一个明确的终点，所以不能贪心。看到名字里有 Jump Game，不要条件反射地往贪心上想。
这类题的通用识别方式很简单：如果动作只能从高状态流向低状态，或者从大值流向小值，并且求的是最长路径，就应该立刻联想到 DAG 最长路。再进一步，如果能找到天然的偏序关系，排序往往是解题的关键。
5.2 识别“天然拓扑序”型 DP
动态规划有很多种套路，其中最容易被忽略的一种就是“计算顺序由偏序关系决定”。比如二维矩阵上的滑雪问题：只能从高处滑向低处，求最长滑行距离。常规做法是记忆化搜索，但其实也可以把所有格子按高度排序，按照高度从低到高递推。这和 1340 的思路完全一致。
再比如最长递增子序列，虽然经典解是二分，但如果我们用一维 DP，转移方向就是按数值大小排列。只要题目里有限制“严格大于/严格小于/大于等于/小于等于”，就要意识到这可能是一张 DAG，排序后就得到拓扑序。
5.3 数据范围变大之后怎么优化
如果n和d都变成 10 万，O(n*d)就会超时。这时候可以进一步优化。先想清楚每个点能跳到的区间：向左看，最多能走到第一个高度大于等于arr[i]的位置再往前一个；向右同理。这个“第一个大于等于当前值的位置”可以用单调栈在O(n)内预先算出来。然后每个点 i 的合法跳跃区间就是左右两个边界和i-d、i+d的交集。
按高度从小到大处理时，我们要查询这个区间内已经算好的dp最大值。因为区间是动态的，节点在逐个解锁，所以需要线段树或树状数组维护区间最大值。每次先查区间最大值，再加 1 得到当前dp[i]，然后更新到线段树上。总复杂度降到O(n log n)。这个进阶思路很值得理解，尤其当你以后遇到 n 更大的变体题时，就不会手足无措。
5.4 同类题型的启发
做完这题再回头看，会发现它给的框架非常典型：一个数组，一组限制，求最长路径。限制是方向性的，方向来源于值的比较。以后遇到类似的题，第一步先画出边的方向，第二步找拓扑序，第三步设计 DP。如果发现没有明确拓扑序，就考虑记忆化搜索或者其他转化。
我个人在实际操作中的体会是：困难题并不一定意味着状态设计多复杂，很多时候难在你看不清计算顺序。1340 这道题，从“只能从高处往低处跳”这句话里挖出拓扑序，整个实现就简单到让人意外。 97ms 不是终点，但它让我确认了一件事：一行排序，抵得上十行递归。希望这篇记录能让你少走一点弯路。
