Hard

题目描述

你的赛车起始停在位置 0 且速度为 +1 的无限数轴上。你的赛车可以进入负数位置。你的赛车会根据一系列由 ‘A’（加速）和 ‘R’（倒车）组成的指令自动行驶：

当你得到指令 ‘A’ 时，你的赛车按以下方式行驶：

  • position += speed
  • speed *= 2

当你得到指令 ‘R’ 时，你的赛车按以下方式行驶：

  • 如果你的速度是正数，则 speed = -1
  • 否则 speed = 1

你的位置保持不变。

例如，在执行指令 “AAR” 后，你的赛车先后位于 0 –> 1 –> 3 –> 3，速度先后为 1 –> 2 –> 4 –> -1。

给你一个目标位置 target，返回能到达目标位置的最短指令长度。

示例 1：

输入：target = 3
输出：2
解释：
最短指令序列为 "AA"。
你的位置从 0 --> 1 --> 3。

示例 2：

输入：target = 6
输出：5
解释：
最短指令序列为 "AAARA"。
你的位置从 0 --> 1 --> 3 --> 7 --> 7 --> 6。

提示：

  • 1 <= target <= 10^4

解题思路

这是一个经典的动态规划问题，我们需要找到到达目标位置的最短指令序列。

核心思路

对于任意位置 i，我们可以从以下几种方式到达：

  1. 直接加速：连续执行 k 次 ‘A’，可以到达位置 2^k - 1
  2. 超调回退：如果直接加速会超过目标，我们可以先加速超过目标，然后倒车回来
  3. 提前回退：在到达 2^k - 1 之前就回退，然后重新加速

状态转移方程

设 dp[i] 表示到达位置 i 的最短指令长度。对于位置 i，我们考虑：

  1. 情况1：如果存在 k 使得 2^k - 1 = i，则 dp[i] = k
  2. 情况2：先加速 k 次到达位置 2^k - 1 > i，然后倒车回退到 i
    • 指令长度：k + 1 + dp[2^k - 1 - i]
  3. 情况3：先加速 k-1 次，回退，再加速 j 次，最后到达 i
    • 指令长度：(k-1) + 1 + j + 1 + dp[i - (2^(k-1) - 1) + (2^j - 1)]

我们取所有可能情况的最小值。

推荐解法：记忆化搜索，相比于自底向上的动态规划更直观易懂。

代码实现

class Solution {
public:
    int racecar(int target) {
        vector<int> dp(target + 1, -1);
        return helper(target, dp);
    }
    
private:
    int helper(int target, vector<int>& dp) {
        if (target == 0) return 0;
        if (dp[target] != -1) return dp[target];
        
        // 找到最小的k使得2^k-1 >= target
        int k = 1;
        while ((1 << k) - 1 < target) k++;
        
        // 情况1：恰好到达
        if ((1 << k) - 1 == target) {
            return dp[target] = k;
        }
        
        // 情况2：超调后回退
        int result = k + 1 + helper((1 << k) - 1 - target, dp);
        
        // 情况3：提前回退
        for (int j = 0; j < k - 1; j++) {
            int pos = (1 << (k - 1)) - 1 - ((1 << j) - 1);
            result = min(result, (k - 1) + 1 + j + 1 + helper(target - pos, dp));
        }
        
        return dp[target] = result;
    }
};

class Solution:
    def racecar(self, target: int) -> int:
        memo = {}
        
        def dp(pos):
            if pos == 0:
                return 0
            if pos in memo:
                return memo[pos]
            
            # 找到最小的k使得2^k-1 >= pos
            k = 1
            while (1 << k) - 1 < pos:
                k += 1
            
            # 情况1：恰好到达
            if (1 << k) - 1 == pos:
                memo[pos] = k
                return k
            
            # 情况2：超调后回退
            result = k + 1 + dp((1 << k) - 1 - pos)
            
            # 情况3：提前回退
            for j in range(k - 1):
                pos_after_retreat = (1 << (k - 1)) - 1 - ((1 << j) - 1)
                result = min(result, (k - 1) + 1 + j + 1 + dp(pos - pos_after_retreat))
            
            memo[pos] = result
            return result
        
        return dp(target)

public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    
    public int Racecar(int target) {
        return Helper(target);
    }
    
    private int Helper(int target) {
        if (target == 0) return 0;
        if (memo.ContainsKey(target)) return memo[target];
        
        // 找到最小的k使得2^k-1 >= target
        int k = 1;
        while ((1 << k) - 1 < target) k++;
        
        // 情况1：恰好到达
        if ((1 << k) - 1 == target) {
            memo[target] = k;
            return k;
        }
        
        // 情况2：超调后回退
        int result = k + 1 + Helper((1 << k) - 1 - target);
        
        // 情况3：提前回退
        for (int j = 0; j < k - 1; j++) {
            int pos = (1 << (k - 1)) - 1 - ((1 << j) - 1);
            result = Math.Min(result, (k - 1) + 1 + j + 1 + Helper(target - pos));
        }
        
        memo[target] = result;
        return result;
    }
}

var racecar = function(target) {
    const memo = new Map();
    
    function dp(pos, speed) {
        if (pos === target && speed === 1) return 0;
        if (Math.abs(pos) > 2 * target) return Infinity;
        
        const key = pos + ',' + speed;
        if (memo.has(key)) return memo.get(key);
        
        let result = Infinity;
        
        // Option 1: Accelerate
        result = Math.min(result, 1 + dp(pos + speed, speed * 2));
        
        // Option 2: Reverse
        const newSpeed = speed > 0 ? -1 : 1;
        result = Math.min(result, 1 + dp(pos, newSpeed));
        
        memo.set(key, result);
        return result;
    }
    
    return dp(0, 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(target × log target)
空间复杂度O(target)

说明：

  • 时间复杂度：每个位置最多计算一次，每次计算需要遍历 O(log target) 种可能的回退方案
  • 空间复杂度：记忆化存储需要 O(target) 空间，递归栈深度最大为 O(log target)