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 - 1（m 从 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 = t
int n = 32 - Integer.numberOfLeadingZeros(t); // 即 floor(log2(t)) + 1
int 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 = 3
  2^2 - 1 = 3 → 直接 AA → 输出: 2

• 输入: target = 6

  • n = 3, 2^3 - 1 = 7
  • 策略一: 3 + 1 + dp = 4 + 1 = 5
  • 策略二: 枚举 m=0,1 → 最小为 5
  • 输出: 5（指令 “AAARA”）

⏱️ 复杂度分析

• 时间: O(T log T) —— 每个 t 枚举最多 log t 次
• 空间: O(T) —— DP 数组

💡 为什么不用 BFS？
虽然 BFS 直观（状态 = (pos, speed)），但状态空间大（速度指数增长），即使剪枝也较慢。DP 利用数学性质，效率更高，是 LeetCode 官方推荐解法。

需要 BFS 版本 或 详细图解 吗？欢迎继续提问！