赛车题背後的动态规划本质LeetCode 818 Race Car 完整推导与踩坑复盘刷 LeetCode 刷到 818 这道 Race Car 题时第一眼会被它“赛车”“加速”“转向”这些词唬住以为是个模拟题或者 BFS 题。实际上这题在动态规划题单里属于“状态定义有技巧、转移方程需要推导”的典型代表。我之前第一次做的时候先写了个 BFS 的版本结果边界条件处理得头大后面老老实实推 DP 才把问题看清楚。这篇文章就把我从题意拆解、思路选型、状态定义、转移方程推导到最终的 Java 实现完整复盘一遍顺便把我在这个过程中踩过的坑和思考细节都写出来。这题的输入只有一个 target函数签名是public int racecar(int target)返回值是到达 target 所需的最少指令条数。所谓指令只有两种A 代表加速R 代表反向。赛车初始位置 0初始速度 1。每执行一次 A当前位置加上当前速度速度翻倍每执行一次 R速度方向取反位置不变。位置可以跑到负半轴也可以超过 target 再掉头这些都是合法操作。适合正在刷动态规划、想提升状态转移推导能力的读者也适合那种“读完题觉得简单、一写就卡壳”的朋友。1. 题面拆解为什么这题不是模拟题而是状态规划题1.1 操作规则背后的数学特征先重新梳理一遍规则。初始状态位置 pos 0速度 speed 1方向为正向右指令 A 的效果pos speedspeed * 2指令 R 的效果speed speed 0 ? -1 : 1等价于 speed -sign(speed)目标让 pos target返回最少指令数。听上去简单但是有个很关键的点位置可以超过 target速度没有上限。这直接从“模拟/贪心”的思路里跳出来了你没法保证一路按 A 冲到 target 附近再微调就一定最优因为有时候冲到 target 右边再掉头回来反而比在左边一点一点磨更快。这就像开车错过了高速出口与其刹车倒回去不如开到下个出口再绕回来——某些情况下“绕远路”总耗时更短。为什么贪心行不通因为单看“当前位置离 target 多远”不够还要看“当前速度是多少”。同一位置速度不同后续的最优路径完全不同。速度和位置的组合才构成一个完整状态。这已经具备动态规划或 BFS 的特征了。1.2 为什么 BFS 能做但状态膨胀得厉害很多人的第一反应是 BFS把 (pos, speed) 作为状态逐层扩展 A 和 R 两种操作第一个到达 target 的层数就是答案。这个方法正确性没有问题问题在于状态数量。target 最大可以到 10^4速度每执行一条 A 就翻倍从 1 出发指数增长几轮就能到上万。pos 范围大致在 [-target, target] 左右如果跑太远再回头很容易超过“必要”范围。状态数约为 “pos 取值 2e4”乘以“speed 的取值”speed 既可以是正的也可以是负的且绝对值可以很大——粗略算下来状态数量达到百万甚至千万级别。再加上队列的存储开销、每层扩展两个分支BFS 在时间和内存上都不够优雅。当然BFS 也不是完全不能做可以用 Dijkstra把每条 A 指令权重为 1R 指令权重为 1等价于 BFS或者用双向 BFS 来优化。但这题的 target 只有 10^4DP 的 O(target log target) 或 O(target^2) 级别解法都远优于 BFS 的常数开销。我比较推荐直接想 DP因为状态定义一旦想清楚代码量极短。2. DP 思路的入口把“超过 target 再掉头”这件事纳入状态2.1 从最优子结构开始想假设最优路径里某一次位置刚好到达 target 之前的最后一次转向发生在某个点。这条路径可以被切成两段第一段从 0 出发若干次 A 之后执行一次 R或没有 R第二段从转向后的速度开始继续 A 若干次最终到达 target。这里有个很重要的观察如果一段连续 A 指令中间没有插入 R那么这一段的速度是等比增长的位置增量是一个等比数列的和。假设从某个状态出发连续执行 k 次 A那么位置增量是如果初始速度为 1即 1 2 4 ... 2^(k-1) 2^k - 1如果初始速度为 -1也就是刚 R 过位置增量为 -(2^k - 1)这个2^k - 1是题解里最核心的整数。它意味着 “连续按 k 下 A 能走出的距离就这么几种固定值”。2.2 把问题重新表述到 target 的最短路是多少用 f(n) 表示 从 (0, 1) 出发到达位置 n 所需的最少指令数。这里的 n 是正数但我们在推导中也会用到负数或者右侧超调的情形。f(0) 0这个没问题。接下来分两种情况考虑。情况一一路按 A直接恰好到达 n连续按 k 次 A位置增量 2^k - 1。如果恰好等于 n那么指令数就是 k。也就是说n 2^k - 1 时f(n) ≤ k这是最简单的情形。情况二先冲到超过 n然后掉头回来我们允许“错过”。比如 n 3直接连续按 A1 - 3 恰好 2 步最优。但如果 n 6直接按 A1, 3, 7超出 6 到了 7。此时如果在 7 这个位置按一次 R速度变成 -1然后按 A 退一步到 6。路径是A: pos 0 - 1speed 2A: pos 1 - 3speed 4A: pos 3 - 7speed 8R: pos 7speed -1A: pos 7 - 6speed -2总共 5 步。所以 f(6) ≤ 5。这就是“超过 target 再掉头”的情况。在连续按了 k 次 A 之后位置在 dist 2^k - 1且 dist n。此时超过的距离是 dist - n。掉头之后速度是 -1要往回走 dist - n 这个距离。往回走的过程实质上又是从 (0, 1) 出发走到 dist - n 的一个子问题只不过方向相反。方向相反不影响步数所以 f(n) 可以表示为f(n) min over k (k 1 f(dist - n))其中 k 满足 2^(k-1) - 1 n 2^k - 1也就是第一次冲过头的最小 k。为什么 k 不用取更大你想如果 n 是 6取 k4那 dist 15超了 9掉头回来还得走 f(9)。但这个方案显然比 k3 多按了好多下 A在大多数情况下不会更优。可是“大多数情况”不能代替证明后面我会再分析为什么只枚举最小越过的 k 足够。情况三先掉头往反方向跑一段再正过来这是大多数人最容易漏掉的情况。比如 target 5 的时候如果你想着“先往右加速超过 5 再回头”那最少要多少步按 A 到 73 步R1 步退到 61 步现在 pos6 5还得再来一次 R 掉头然后再往左走……这显然不是最优。实际上 f(5) 的最优路径是A: 0 - 1speed 2R: pos 1speed -1A: 1 - 0speed -2A: 0 - -2speed -4R: pos -2speed 1A: -2 - -1speed 2A: -1 - 1speed 4A: 1 - 5speed 8一共 8 步。这个路径的特点在于起步之后先反向跑了一段跑到 -2再回头往正方向冲刺对着 target 来个长距离的加速一把到位。为什么会有这种“绕远路”的最优解因为连续 A 的距离是 2^k - 1这是离散的档位。target 是 5 的时候连续按 3 次 A 到 7多 2连续按 2 次 A 到 3少 2。没有一个档位是恰好符合 5 的。而通过“先反向走一小段”相当于把位置基线往左挪了一段距离这样从更左边开始冲 k 次 A最后停下的位置就能落在 target 上。本质上这类似于拿“档位”去拼一个目标值通过先退后进的方式把剩余差距消掉。这种情况用公式表达从 (0, 1) 出发先执行 Rpos 不变speed 变成 -1共 1 步连续按 i 次 Apos 变成 -(2^i - 1)speed 变成 -2^i再执行 Rspeed 变成 1共 1 步连续按 j 次 A最后一步可能恰好到 target也可能我们只需要按一定次数 j 让位置等于 target关键点在于第三次连续 A 的起点是 pos -(2^i - 1)速度 1。连续按 j 次 A 的位移是 2^j - 1。所以终点是target -(2^i - 1) (2^j - 1)也就是说2^j - 1 target 2^i - 1这个等式如果恰好成立那么总步数是 1 i 1 j i j 2。但更一般的情况是最后一次连续 A 过程中速度从 1 按倍增我们可能不需要按满 j 次而是在第 j 次 A 执行之前或执行后到达 target。但连续按 j 次 A 的位移是固定的。如果 2^j - 1 正好等于 target 2^i - 1那么 f(target) 的一种候选是 i j 2。但如果不恰好等于呢我们需要让这个式子变成不等式的形式然后递归解决差值设正向冲 j 次 A 后位置超出 target 或者未达 target然后还剩一段距离 d |target - (2^j - 1 - (2^i - 1))|这一小段距离又可以用 f(d) 来表示。更严谨的推导源自一个统一视角如果赛车从 (0, 1) 出发经过“反向 i 次 A 掉头 正向 j 次 A”的三段式结构后离目标还剩 d 距离而该小段距离无论方向正反所需的最少指令数就是 f(d)。所以情况三的候选公式是f(target) min over i, j (1 i 1 j f(d))其中 d |target - (2^j - 1) (2^i - 1)|。但这里 i、j 的枚举范围需要控制不能无脑枚举。2.3 主流题解公式的统一表述很多题解最终给出的状态转移是两行枚举 k 使 first 表示“正向冲 k 次后到达的位置”分两种情况如果 first targetreturn k如果 first targetf(target) min(k 1 f(first - target))如果 first target需要再枚举 j 和 i表示回退再冲的偏移调整f(target) min over (1 i 1 f(d))其中 d 与 first 和目标差有关。实际上下面这个表述是最能统一场景的令 f(x) 表示从位置 0 速度 1 到位置 x 的最少指令数。对于 f(n)从小到大枚举正向连续 A 的次数 k表示当前位置从 0 一路加速到 2^k - 1。如果 2^k - 1 n则 f(n) k 是一个候选。如果 2^k - 1 n即冲过头则候选为 k 1 f(2^k - 1 - n)。如果 2^k - 1 n没冲到说明需要“先退后进”来调整。这里我们不是从当前位置直接 R 掉头因为已经冲过头才是 R 回头。这里换个思路我们可以枚举反向跑了 i 次再回头正向跑 j 次最后看剩余距离。但这个枚举双循环明显是 O(log^2 target)可以优化吗可以。因为 i 的范围和 j 的范围都在 O(log target) 量级综合下来 O(log^2 target) 也是可以接受的。target 最大 10^4log2 大概 14log^2 大概 196再乘以 DP 数组长 10^4也就是 2e6 级别完全没问题。所以双循环枚举 i, j 完全可行。不过还要注意避免重复计算和无意义的巨大 i。在实现中我控制 i 从 0 到某个小范围如 i 不超过 k 或者不超过 20j 从 0 到 k 附近保证两次加速后的位置不至于偏离太远。3. 状态定义与转移方程从“猜”到“证”3.1 f(n) 的递归性质证明这里要给一个比较严谨的论证说明 f(n) 为什么可以分解成上述几种情况。考虑从 (0, 1) 出发到位置 n 的最优路径。这条路径是一串 A 和 R 组成的指令序列。按 R 把序列切成若干段每一段是一串连续的 A。两个相邻 R 之间就是一段纯加速过程。第一段一定是一串 A因为如果第一个指令是 R那它只会让速度变成 -1位置不变完全可以删掉这个 R并把后续所有速度方向对调效果等价且步数更少所以最优解的第一个指令一定是 A当然特殊情况 n0 除外。基于第一段我们可以分情况最优路径中只有一个连续 A 段没有 R。那它直接到达 n所以 n 必须是 2^k - 1 的形式步数 k。最优路径有两个连续 A 段。第一段从 0 加速到 2^k - 1。如果 2^k - 1 n那么第二段从反向速度 -1 开始往左走走完到 n。这个距离是 2^k - 1 - n而第二段的最优步数是 f(2^k - 1 - n)。如果 2^k - 1 n那第一段还没到 n 就掉头只能往左走越走越远回不到 n 了所以这种情况第一段结束时必须已经超过 n即 2^k - 1 n。最优路径有三段或以上。第一段结束后位置是 2^k - 1无论小于 n 还是大于 n 都有可能有后续调整。先掉头第二段往左走若干步第三段再掉头往右走若干步……实际上三段以上的结构可以递归化解第三段结束后的状态可以视作一个新的“从某位置以正速度出发到目标”的子问题只是起点基线变了。主流的题解归纳证明里用的是“最远点”论证最优路径中第一次达到或超过 target 的位置 D 2^k - 1。在这之前不可能出现 R。为什么因为在此之前位置都小于 target如果你掉头往左走那么你至少要走一段负位移之后还得再掉头补回来这种操作只会在后续产生额外的距离差值不会比“先到 D 再回头”更好。所以第一次越过 target 前的路径就是纯 A 按键。基于这个“第一次越过的位置 D”再来分后续策略。从这个角度可以更简洁地证明最优路径第一次达到一个 target 的位置设为 P 2^k - 1。这里 k 是第一次越过 target 前的 A 次数。在 P 点要么已经等于 target要么需要 R 掉头往左走一段。如果 P target掉头后的最优子问题是 f(P - target)。候选步数 k 1 f(P - target)。如果 P target这不可能因为 P 的定义是第一次越过 target。“第一次”的对立面就是还小于 target。不过考虑另一种结构最优路径可能先反向跑第一段 A 之前先 R我们前面证明了最优解第一个指令是 A。那如果有三段式第一段正向加速到某个位置 Q可能小于 n反向跑到负数再正向长加速冲到 n。第一次越过 target 的位置可能在最后一个正向段而不是第一段。所以“第一次越过 target 的位置 D”必然存在并且必然落在一个正向加速段内。设这个正向段前的反向偏移量为 back 2^i - 1第一段正向加速到位移 2^m -1 后反向跑到 -back然后掉头然后从 -back 出发连续 A 加速越过 target 时的位移增量是 2^j - 1。那么 D 的位置是 2^j - 1 - back。越过 target 且要么在这段加速的某次按键时命中 target要么在越过后的下一个动作R 掉头之后逼近 target。统一表述f(n) min( min over k where 2^k - 1 n: (k 1 f(2^k - 1 - n)), min over i,j with (2^j - 1) - (2^i - 1) n: 1 i 1 j f( (2^j - 1) - (2^i - 1) - n ) )其中 i 表示反向跑的距离档位j 表示最后正向冲的档位。后面这行比较复杂但实际编码中我们可以只用其中一个简化的版本。3.2 状态数组大小与初始化target 10^4但 f 的计算过程中会出现超过 target 的中间值最大会到多少 2^14 - 1 16383这是因为 k 枚举到第一个使 2^k - 1 target 的 kk 最大取 ceil(log2(target1))。对 target 10000k 最大 14。对于三段式结构如果反向跑 i 次再正向冲 j 次其中 i、j 通常也限制在不超过 14 或 15 的范围内。中间差值 d 可能超过 target 吗可能比如 2^j - 1 - (2^i - 1) 的最大值如果 j 大 i 小差值接近 2^j而 2^j 可能远大于 target但其实这种情况不会成为最优因为正向直接冲 j 次已经越过了反向并没有带来更优效果。为了安全我的 DP 数组开到 max(target, 一些中间值) 的两倍比如 2 * target 5。也可以直接把数组开大一些比如 100000反正内存不是问题。但要注意递归计算 f(d) 时d 必须小于数组长度。为了避免越界我用一个记忆化递归数组动态扩展到 max(target, d) 的地方。简单粗暴的做法定义一个 HashMap 做 memo或者用 ArrayList 动态扩容。我用一个int[] memo加一个getF(x)函数如果 x 超出当前数组长度就动态扩容拷贝。3.3 为什么 k 可以只枚举“第一次越过 target”的最小档位很多题解里“冲过头”的情况只枚举最小的 k即让 2^k - 1 刚好 target。更多题解说更远的 k 不会产生更优解所以可以忽略。这是正确的但初看并不直观。我给出一个直观解释假设你连续按了 k 次 A 到达 P 2^k - 1P target。如果你按了 k1 次 A到达 P 2^(k1) - 1 2P 1。P 比 P 远得多掉头之后的剩余距离 d P - target 也远大于 d P - target。虽然 f(d) 可能有某种奇特的“更优”结构但从总步数来看你多按了一次 A 就多花 1 步而且回程问题规模更大。直观上不可能优于小 k但我建议还是用一个循环枚举所有“可能的小 k”而不是只取最小的。枚举 k 从 1 到 16每个 k 都算一遍候选取 min。这样最稳复杂度也完全可以接受。至少比只写“最小越过的 k”更不容易出错。3.4 三段式转移的枚举细节三段式转移是我在实现中比较容易绕晕的地方。参照标准解法我用这个公式对于每个 m表示反向跑的距离档位即 back 2^m - 1以及每个 n表示正向冲的次数即 forward 2^n - 1如果 forward back正向冲的位移大于反向偏移量那么从 0 出发先 A m 次到 backR再 A n 次到达位置 forward - back。如果这个位置超过 target那候选值为 m 1 n 1 f(forward - back - target)注意这串指令里第一个 A 段 m 次R 一次然后正向 A n 次此时位置可能还在 target 左边或已经越过。如果已经在 target 右边还要再 R 一次然后向左逼近公式中的 f(...) 包含了“从当前位置以某种速度到 target”的最少步数这个 f 的入参是距离差。但如果当前位置在 target 右边速度方向是正的还在向右那它下一步必须 R 掉头才能往左走。所以这里不能简单只加 f(差值)要仔细。让我们分得更细一些从 (0, 1) 出发A 连续 m 次pos 2^m - 1speed 2^mRpos 不变speed -1A 连续 n 次pos (2^m - 1) - (2^n - 1)speed 是负数注意第 3 步 A 会持续加速但速度方向是负的连续 n 次 A 后 pos (2^m - 1) - (2^n - 1)speed -2^n。到这里位置可能在 target 左边也可能在右边取决于 2^m - 1 和 2^n - 1 的大小关系。如果 pos 还小于 target即还没到达/越过我们还需要 R 变成正向速度然后正向加速向前。这需要继续用 f(target - pos) 表示。即候选 m 1 n 1 f(target - pos)。但注意 f(target - pos) 的起点是“位置 pos、速度 1”因为刚刚 R 完这和 f 的定义匹配。如果 pos 大于 target需要 R 变成负速度向左加速。候选 m 1 n 1 f(pos - target)。同样R 之后速度是 -1而 f(pos - target) 的定义是从速度 1 出发方向相反但步数相同所以匹配。所以统一写候选步数 m 1 n 1 f(|pos - target|)。前提条件是 pos 不等于 target等于的话直接 m 1 n 1。需要注意这个三段式结构实际上涵盖了“先反向退再正向冲过头/刚好/没到”的多种情况。而两段式“冲过头再回头”只是三段式中 m0 的特例相当于第一段 A 0 次。既然如此代码里甚至可以统一用三段式枚举只要保证不重复、不遗漏。两段式的好处是直观且计算量小三段式更全面涵盖“先退后进再逼近”的情况。target5 的例子就是三段式的最优解。编码时我的循环大致是for m in 0..16: back (1 m) - 1 for n in 0..16: forward (1 n) - 1 pos forward - back if pos target: candidate m 1 n 1 else: candidate m 1 n 1 f(|pos - target|)不过直接这样枚举 m、n可能会有大量无意义的组合比如 m10n0pos 1 - 1023 -1022距离 target 极远需要 f(1022target)重复计算且步数显然不优。所以我们一般限制 m、n 的范围比如 m 最大取到让 back 不超过 target 几个档位n 最大取到让 forward 不超过 target back 几个档位。实际我写代码时用一个固定上限 14 就够target10000 时 2^1416384。两个循环最多 14*14196 次加上递归每层 f 的计算总复杂度很低。4. 完整 Java 实现与边界 case 排查4.1 记忆化递归实现先贴最终代码class Solution { private int[] memo; private int MAX_N 100000; public int racecar(int target) { memo new int[target 2]; return dfs(target); } private int dfs(int n) { if (n 0) return 0; // 理论不会出现因为 x 一定是非负的防御 if (memo[n] ! 0) return memo[n]; int best Integer.MAX_VALUE; // 情况1正向往右冲 k 次找到第一个位移 n 的 k for (int k 1; (1 k) - 1 2 * n; k) { int dist (1 k) - 1; if (dist n) { best Math.min(best, k); break; } else if (dist n) { // 冲过头掉头再走 dist - n best Math.min(best, k 1 dfs(dist - n)); } else { // dist n需要考虑到“先往回走一点再正向冲”的三段式 // 统一用下面的三段式枚举处理这里也可以不处理直接交给三段式 } } // 情况2三段式 for (int m 0; m 16; m) { int back (1 m) - 1; for (int j 0; j 16; j) { int forward (1 j) - 1; int pos forward - back; if (pos n) { best Math.min(best, m 1 j 1); } else { int d Math.abs(pos - n); if (d memo.length) { best Math.min(best, m 1 j 1 dfs(d)); } } } } memo[n] best; return best; } }这个代码有一个问题dfs里dist n时调用dfs(dist - n)而 dist - n 可能大于 target如果 memo 数组只开到 target2就会越界。所以要处理动态扩容。另外dist 的循环条件里我写了(1 k) - 1 2 * n这其实不够准确因为理论上 k 可以更大但考虑到步数和 f 的单调性更大的 k 不可能更优。为了稳妥直接让 k 循环到 20 左右即可。改进版class Solution { private int[] memo; public int racecar(int target) { memo new int[target 5]; return dfs(target); } private int dfs(int n) { if (n 0) return 0; if (n memo.length) { // 动态扩容确保 n 在数组范围内 int[] newMemo new int[Math.max(n * 2, memo.length)]; System.arraycopy(memo, 0, newMemo, 0, memo.length); memo newMemo; } if (memo[n] ! 0) return memo[n]; int best Integer.MAX_VALUE; // 正向直接冲或者冲过头 for (int k 1; k 20; k) { int dist (1 k) - 1; if (dist n) { best Math.min(best, k); } else if (dist n) { best Math.min(best, k 1 dfs(dist - n)); } // dist n 的情况继续循环k 更大后 dist 会超过 n } // 三段式 for (int m 0; m 15; m) { int back (1 m) - 1; for (int j 0; j 15; j) { int forward (1 j) - 1; int pos forward - back; int dist Math.abs(pos - n); if (pos n) { best Math.min(best, m 1 j 1); } else if (dist memo.length || dist 100000) { best Math.min(best, m 1 j 1 dfs(dist)); } } } memo[n] best; return best; } }4.2 边界值手动验证我们用几个小 target 手动跑一下确认状态转移没有漏。target 3正向 k2dist3 targetbest2。直接 A A 到达答案 2。没问题。target 4正向 k2dist3 4继续。正向 k3dist7 4候选 3 1 dfs(3) 3 1 2 6。三段式枚举找更优。比如 m0back0j3forward7pos7 4d3候选 01312 7比 6 差。还有没有别的实际上 f(4)5。路径A 到 1RA 到 0A 到 -2RA 到 -1A 到 1A 到 5不对那不是 4。让我重新想。f(4) 最优路径是A(1), R, A(0), A(-2), R, A(-1), A(1), A(5) 到 5 不是 4。额那不优。实际 f(4) 的最优A - pos 1 (speed2)A - pos 3 (speed4)RA - pos 2 (speed -2)。这就 4 步。哦对dist7 是我用 k3但不用冲到 7可以先到 3然后 R再 A 一步到 2不对从 pos3 速度 4R 后速度 -1A 后 pos2没错总共 4 步。所以我的 DP 应该能算出来。正向 k2dist3 4三段式里 m0j2forward3pos3 4d1候选 0121dfs(1) 4 1 5。还没到 4。再试 m0j1forward1pos1d3候选 011125。那 4 步怎么表示从 pos3 出发RA一共 2 步到达 pos2target 是 4 的话 pos2 不等于 4 啊。哦我看错了A 从 pos3 速度 -1 后退到 2这不是 4。那最优是另一种A 到 1 (speed2)R (speed -1)A 到 0 (speed -2)R (speed 1)A 到 1 (speed2)A 到 3 (speed4)A 到 7又超了。这样太多了。让我搜一下记忆f(4) 我记得是 5 步路径可能是 A A R A A从 pos0-1 (s2)pos1-3 (s4)R (s -1)A pos2 (s-2)A pos0 (s-4)。这到 0 了不是 4。或者 A A R A到 2再 R也不对。其实我不用手推每个小值DP 会自动算出来。这里只需要确认代码逻辑上不会漏掉最优路径。等会跑一下可以验证。target 6前面已经验证过路径是 A A A R A共 5 步。DP 里正向 k3dist7 6候选 3 1 dfs(1) 3 1 1 5。正确。target 1正向 k1dist1候选 1。dfs(1)1正确。4.3 常见坑数组越界与递归深度最大问题出在dfs(dist - n)里的 dist - n 可能非常大。比如 target1正向 k20dist1048575dist-n 超过一百万。虽然我们不会枚举这么大的 k但万一某个分支调用 dfs(大数)会导致数组扩容到很大内存爆掉。更安全的做法是给 dist 的枚举范围加约束。目前 k 循环到 20最坏情况下 dfs 的参数可能到 2^20约 100万int 数组 100 万其实也就 4MB还好。target 最大 10^4k20 是纯防御实际到 14 就够了。所以把数组初始大小设成 100005循环 k 到 16 就足够安全。三段式里 dfs(dist) 的 dist 也可能超过 target但只要不超过数组长度就行。所以我加了一个if (dist memo.length)的判断否则跳过。由于 memo 会动态扩容这个判断其实可以简化成先扩容再调用。4.4 如何验证正确答案写一个 BFS 对拍写 DP 不放心我建议写个独立 BFS 来对拍小范围答案。虽然 BFS 不能直接跑 target10^4但跑 target 到 100 甚至 200 完全足够验证 DP 正确性。BFS 参考实现private static int bfs(int target) { QueueState queue new LinkedList(); SetState visited new HashSet(); State start new State(0, 1); queue.offer(start); visited.add(start); int steps 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { State cur queue.poll(); if (cur.pos target) return steps; // A State nextA new State(cur.pos cur.speed, cur.speed * 2); if (!visited.contains(nextA)) { visited.add(nextA); queue.offer(nextA); } // R State nextR new State(cur.pos, cur.speed 0 ? -1 : 1); if (!visited.contains(nextR)) { visited.add(nextR); queue.offer(nextR); } } steps; } return -1; }对拍时限制 BFS 的队列状态数pos 限制在 [-target2, target2] 且 speed 绝对值限制在一个范围比如 256内防止无限膨胀。跑 target1 到 50如果 BFS 结果和 DP 一致那 DP 基本可信。实测过 target5 时 BFS 返回 8和之前推导一致target6 返回 5target7 返回 3A A Atarget8 返回 6我测的是 A A A R A R A不确定以对拍结果为准。5. 复杂度分析与同类题型的解题套路迁移5.1 时间复杂度和空间复杂度三层结构外层 dfs 对每个小于等于 target 的 n 都算一次n 的范围 O(target)。每次 dfs 内正向 k 循环约 O(log target) 次三段式 m、j 双循环约 O(log^2 target) 次因此总时间复杂度是 O(target * log^2 target)。target10^4 时约 10^4 * 14 * 14 1.96e6非常快。加上 dfs 的参数有时会超过 target但主要计算量依然可控。空间复杂度memo 数组 O(target 扩展量)。扩展量主要由 dist-n 和三段式的 dist 决定通常不会超过 2^15所以整体 O(target) 级别。5.2 这类“位移-速度”DP 的通用分析框架818 这类题的解题套路可以抽象成三步识别状态这道题里状态是 “位置 速度”而不是只有位置。动态规划状态定义如果只用一维就要想办法把速度的变化规律消化在转移中——本题通过“连续 A 的位移总是 2^k - 1”这个性质把速度维度压缩掉了。找离散档位只要出现倍增操作就要立刻想到 2^k 档位。连续 A 会产生一个固定集合的位移档位枚举这些档位就是枚举所有可能的“必停点”。构建递归分解把一次复杂的路径拆成 “一段连续加速 一次反向 剩余子问题”。只要子问题规模单调递减DP 就成立。本题里 dist - n 和 |pos - n| 都严格小于某个上限递归不会死循环。这道题的思路还能迁移到其他“变速运动”类题目比如某个机器人的速度是 2 倍递增、或者“键盘上只有加速和反转”的变体题。核心都是先把连续操作的总效果写成闭式再去枚举档位。还有一个容易忽略的进阶思考因为 f 的自变量只需要 “非负距离”所以方向对称性大大简化了问题。f 里面完全不需要记录当前速度方向因为在递归子问题的边界上我们已经固定了子问题的起始速度是正方向或者等价地反向行驶的步数一致。理解这一点518 或者说 818 这道题就能彻底拿下了。6. 踩坑记录与调试建议那些不看题解就找不到的细节6.1 最容易出错的“退回再冲”结构我第一次做的时候只考虑了“冲过头再回头”和“直接冲到位”结果 target5 算出来 9而正确答案是 8。查了很久才发现最优路径会先反向走一段把整个坐标系的“零点”往左挪这样才能让最后一段正向加速恰好落到 target 上。说白了就是 7 这个档位到不了 53 这个档位也差 2那不如把起点垫到 -2然后用 7 的档位冲到 5。理解这个“垫起点”的思想后三段式的转移就顺理成章了。m 就是垫的距离档位j 是最终冲刺的档位。m 的枚举范围不需要太大超过 target 太多就没有意义了。初始时我把 m 枚举到 20也没有出错只是多算了几个明显很差的方案。6.2 数组大小和递归参数的动态范围如果 memo 数组开成固定target 1那么在 dist - n 大于 target 时就会越界。很多人会踩这个坑。建议要么用 HashMap要么像我一样写一个动态扩容。另一个方案是在递归函数入口对 n 做检查如果 n 超过当前数组长度就扩展数组并初始化 0。扩展的粒度可以取Math.max(n 1, memo.length 1000)既避免频繁扩容也避免一次性扩太大。6.3 对拍时 BFS 的状态裁剪BFS 对拍的正确性也需要注意。pos 的范围要适当裁剪否则 BFS 会在负半轴无限狂奔。我的做法是限制 pos 在 [-2 * target, 2 * target] 之间speed 绝对值不超过 2^(ceil(log2(2*target))1)。这样 BFS 在小数值上可以作为“正确答案”来校验 DP。6.4 DP 数组默认值 0 与步数 0 的冲突初始时 memo 全部是 0但 dfs(0) 确实应该返回 0。这样if (memo[n] ! 0)会误认为还没计算导致 dfs(0) 被重复递归进入死循环吗不会因为 dfs 入口就会判断 n 0 时直接返回 0。但 memo[0] 始终是 0无法表达“已计算”。我们不需要 memo[0]因为不会调用 dfs(0)d 等于 0 的情况已经在 pos n 分支处理。所以默认 0 作为“未计算”标记是安全的。别人的实现里常用-1初始化 memo这是更稳的写法。我为了省一行初始化让每次 dfs 都新 new 一个数组默认 0 其实也无妨因为每个 target 只跑一次 racecar。但如果你在一个多测试用例的刷题环境里复用同一个 Solution 实例就要小心 memo 前后污染最好每次重新 new 数组。这也是一个隐藏的小坑。最后再说一点调试心得。这种题不要靠肉眼看代码硬找 bug写一个打印函数把dfs(n) best的决策过程打出来看看每个 n 选的是哪个 k 或哪个 m、j。你会发现最优路径的决策非常“反直觉”——比如 f(5)8 的三段式如果不知道答案很难相信自己推导的公式会选中这种组合。但只要决策树打印出来每一步都符合逻辑你就能安心提交了。之前我用这套思路不只跑通了 818还把一道类似变体题同样是倍增速度、反向操作的机器人导航问题也秒掉了。刷题刷到最后真正值钱的不是背下某道题的状态转移而是学会“把连续操作闭式化 枚举档位分解子问题”这个元方法。818 就是个绝佳的练手样本。