千问 LeetCode 818.赛车 public int racecar(int target)

LeetCode 818. 赛车Race Car是一道经典的最短指令序列问题目标是从位置 0、速度 1 出发通过 ‘A’加速和 ‘R’倒车指令用最少步数到达目标位置 target。✅ 最优解法动态规划DP 核心观察连续执行 k 次 ‘A’ 指令会走到位置S_k 2^k - 1如果 target 2^k - 1直接返回 k全加速最优。否则考虑两种策略 策略一冲过头再回头用 n 次 ‘A’ 走到 2^n - 1刚好 ≥ target执行 ‘R’ 反向剩余距离(2^n - 1) - target总步数n 1 dp[(2^n - 1) - target] 策略二提前掉头试探后退用 n-1 次 ‘A’ 走到 2^{n-1} - 1未到 target‘R’ 反向再用 m 次 ‘A’ 向后走 2^m - 1m 从 0 到 n-2再 ‘R’ 转回正向此时净前进(2^{n-1} - 1) - (2^m - 1) 2^{n-1} - 2^m剩余距离target - (2^{n-1} - 2^m)总步数(n-1) 1 m 1 dp[剩余] n m 1 dp[…]✅ Java 实现清晰 高效class Solution {public int racecar(int target) {int[] dp new int[target 1];for (int t 1; t tint n 32 - Integer.numberOfLeadingZeros(t); // 即 floor(log2(t)) 1int full (1 n) - 1;if (full t) { dp[t] n; continue; } // 策略一冲过头再回来 dp[t] n 1 dp[full - t]; // 策略二提前掉头枚举后退步数 m int prev (1 (n - 1)) - 1; for (int m 0; m n - 1; m) { int back (1 m) - 1; int remain t - (prev - back); // t - 2^{n-1} 2^m dp[t] Math.min(dp[t], (n - 1) 1 m 1 dp[remain]); } } return dp[target]; }} 示例验证输入: target 32^2 - 1 3 → 直接 AA → 输出: 2输入: target 6n 3, 2^3 - 1 7策略一: 3 1 dp 4 1 5策略二: 枚举 m0,1 → 最小为 5输出: 5指令 “AAARA”⏱️ 复杂度分析时间: O(T log T) —— 每个 t 枚举最多 log t 次空间: O(T) —— DP 数组 为什么不用 BFS虽然 BFS 直观状态 (pos, speed)但状态空间大速度指数增长即使剪枝也较慢。DP 利用数学性质效率更高是 LeetCode 官方推荐解法。需要 BFS 版本 或 详细图解 吗欢迎继续提问