# Race Car
**Difficulty:** HARD
[External](https://leetcode.com/problems/race-car)
Canonical: https://scaleengineer.com/dsa/problems/race-car
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Turing](https://scaleengineer.com/companies/turing), [Anduril](https://scaleengineer.com/companies/anduril)
---
## Problem
Your car starts at position `0` and speed `+1` on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions `'A'` (accelerate) and `'R'` (reverse):

* When you get an instruction `'A'`, your car does the following:  
  * `position += speed`
  * `speed *= 2`
* When you get an instruction `'R'`, your car does the following:  
  * If your speed is positive then `speed = -1`
  * otherwise `speed = 1`  
Your position stays the same.

For example, after commands `"AAR"`, your car goes to positions `0 --> 1 --> 3 --> 3`, and your speed goes to `1 --> 2 --> 4 --> -1`.

Given a target position `target`, return _the length of the shortest sequence of instructions to get there_.

**Example 1:**

**Input:** target = 3
**Output:** 2
**Explanation:** 
The shortest instruction sequence is "AA".
Your position goes from 0 --> 1 --> 3.

**Example 2:**

**Input:** target = 6
**Output:** 5
**Explanation:** 
The shortest instruction sequence is "AAARA".
Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.

**Constraints:**

* `1 <= target <= 104`

# Approaches
## Breadth-First Search (BFS)
This problem can be modeled as finding the shortest path in a state graph. Each state is defined by the car's `(position, speed)`. We start at `(0, 1)` and want to reach any state `(target, *)`. Since each instruction (`A` or `R`) has a uniform cost of 1, Breadth-First Search (BFS) is a natural algorithm to find the shortest sequence of instructions.
**Time:** O(target * log(target)). The number of states visited is the dominant factor. For each state, we do constant work. · **Space:** O(target * log(target)). The queue and `visited` set can store a large number of states. The number of relevant positions is proportional to `target`, and for each position, the number of relevant speeds is proportional to `log(target)`.
**Pros:** Guaranteed to find the shortest path because it explores the state graph layer by layer.; Conceptually straightforward for shortest path problems on unweighted graphs.
**Cons:** The state space `(position, speed)` can be very large, leading to high time and memory consumption.; It relies on heuristic pruning (bounding the position) to be efficient. Finding the optimal bounds can be tricky and may affect correctness if too restrictive.
### Explanation
We use a queue to perform a level-order traversal of the state graph. Each level in the BFS corresponds to one additional instruction, so the first time we reach the target position, we are guaranteed to have used the minimum number of instructions.

The state is represented by a pair `(position, speed)`. We also use a `visited` set to store `(position, speed)` pairs that have already been processed, to avoid cycles and redundant computations.

The algorithm proceeds as follows:
1.  Initialize a queue and add the starting state `(0, 1)`. Mark it as visited.
2.  Initialize `steps = 0`.
3.  While the queue is not empty, process all nodes at the current level.
4.  For each state `(pos, spd)` dequeued:
    -   If `pos == target`, we have found the shortest path. Return `steps`.
    -   Consider the next two possible moves:
        a.  **Accelerate ('A'):** The new state is `(pos + spd, spd * 2)`.
        b.  **Reverse ('R'):** The new state is `(pos, spd > 0 ? -1 : 1)`.
    -   For each new state, if it hasn't been visited and is within reasonable bounds (e.g., `0 <= new_position < 2 * target`), add it to the queue and the visited set.
5.  Increment `steps` after processing each level.

The search space for position is theoretically infinite. We must prune the search by observing that an optimal path is unlikely to travel to positions far beyond the target. A reasonable heuristic is to not explore positions that are much larger than `target` (e.g., `2 * target`).

```java
class Solution {
    public int racecar(int target) {
        // state: {position, speed}
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 1});
        
        // visited: "position,speed"
        Set<String> visited = new HashSet<>();
        visited.add("0,1");
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] currentState = queue.poll();
                int currentPos = currentState[0];
                int currentSpeed = currentState[1];

                if (currentPos == target) {
                    return steps;
                }

                // Action 'A': Accelerate
                int nextPosA = currentPos + currentSpeed;
                int nextSpeedA = currentSpeed * 2;
                String nextStateA = nextPosA + "," + nextSpeedA;
                if (!visited.contains(nextStateA) && Math.abs(nextPosA) < 2 * target) {
                    visited.add(nextStateA);
                    queue.offer(new int[]{nextPosA, nextSpeedA});
                }

                // Action 'R': Reverse
                int nextSpeedR = currentSpeed > 0 ? -1 : 1;
                String nextStateR = currentPos + "," + nextSpeedR;
                if (!visited.contains(nextStateR) && Math.abs(currentPos) < 2 * target) {
                    visited.add(nextStateR);
                    queue.offer(new int[]{currentPos, nextSpeedR});
                }
            }
            steps++;
        }
        return -1;
    }
}
```
### Algorithm
- Model the problem as a shortest path problem on a state graph where each state is `(position, speed)`.
- Use Breadth-First Search (BFS) to find the shortest path from the initial state `(0, 1)` to any state where `position == target`.
- Create a queue and add the initial state `(0, 1)`.
- Use a `visited` set to keep track of states `(position, speed)` that have been enqueued to avoid cycles and redundant computations.
- Process states level by level. The level number corresponds to the number of instructions (path length).
- For each state `(pos, spd)` dequeued:
  - If `pos == target`, the current level is the shortest path length, so return it.
  - Generate two next states:
    1. **Accelerate ('A'):** `(pos + spd, spd * 2)`
    2. **Reverse ('R'):** `(pos, spd > 0 ? -1 : 1)`
  - For each new state, if it has not been visited and is within reasonable bounds, add it to the queue and the `visited` set.
- To make the search feasible, prune the search space by setting bounds on the position. A common heuristic is to not explore positions that are too far from the target (e.g., `abs(position) < 2 * target`).

## Dynamic Programming with Memoization
A more optimized approach uses dynamic programming. Instead of exploring the full `(position, speed)` state space, we can define a recurrence relation for `dp[i]`, the minimum steps to reach position `i`. This exploits the specific structure of the car's movement, where sequences of 'A's lead to positions of the form `2^k - 1`, which act as milestones.
**Time:** O(target * log(target)). For each state `t` from `1` to `target`, we compute its value once. The computation involves a loop that runs `log(t)` times. · **Space:** O(target). The space is dominated by the memoization array of size `target+1` and the recursion stack depth, which is at most `O(log(target))`.
**Pros:** More efficient than a general BFS because it reduces the state space from `(position, speed)` to just `position`.; The DP formulation directly captures the optimal substructure of the problem, leading to a more targeted search.
**Cons:** The recurrence relation is non-trivial to derive and can be complex to understand initially.
### Explanation
We define `dp[i]` as the length of the shortest instruction sequence to reach position `i`. We can compute this using a top-down DP approach (recursion with memoization).

The core idea is that any optimal path consists of sequences of 'A's, punctuated by 'R's. We can reach a target `t` by either going straight to it, overshooting and coming back, or undershooting, reversing for a bit, and then continuing forward.

1.  **Overshoot and Return:** We accelerate `k` times such that we pass the target `t`. The position becomes `2^k - 1 > t`. This takes `k` 'A' instructions. Then, we use one 'R' instruction to reverse direction. Now, we are at `2^k - 1` and need to travel backwards for a distance of `(2^k - 1) - t`. This is equivalent to solving the subproblem for `dp[(2^k - 1) - t]`. The total steps are `k + 1 + dp[(2^k - 1) - t]`.
2.  **Undershoot, Reverse, and Maneuver:** We accelerate `k-1` times to reach `2^(k-1) - 1`, which is less than `t`. This takes `k-1` 'A's. Then we reverse ('R'). Then, we can go backwards for some distance by accelerating `j` times (`j < k-1`). This moves us back by `2^j - 1`. After `j` 'A's, we reverse again ('R'). Now, we are at position `(2^(k-1) - 1) - (2^j - 1)` and need to solve the subproblem for the remaining distance to `t`. The total steps are `(k-1) + 1 + j + 1 + dp[t - (2^(k-1) - 1) + (2^j - 1)]`. We must try all valid `j` and take the minimum.

The final answer `dp[t]` is the minimum of the steps calculated from all these possibilities. We use a memoization array to store the results of `dp[i]` to avoid recomputing them.

```java
class Solution {
    int[] memo;

    public int racecar(int target) {
        // memo array stores the minimum steps to reach position i
        memo = new int[target + 1];
        return dp(target);
    }

    private int dp(int t) {
        if (t == 0) return 0;
        if (memo[t] > 0) return memo[t];

        // k = number of bits in t's binary representation, i.e., ceil(log2(t+1))
        // This means 2^(k-1) <= t < 2^k
        int k = 32 - Integer.numberOfLeadingZeros(t);
        
        // Case 1: Go exactly k 'A's and reach 2^k - 1.
        // If we land exactly on t, this is one possibility.
        if ((1 << k) - 1 == t) {
            return memo[t] = k;
        }

        // Case 2: Go k 'A's to overshoot t, then reverse and come back.
        // Path: A...A (k times) -> R -> ...
        int pos_overshoot = (1 << k) - 1;
        int steps_overshoot = k + 1 + dp(pos_overshoot - t);
        memo[t] = steps_overshoot;

        // Case 3: Go k-1 'A's to undershoot t, reverse, go back j 'A's, reverse, then forward.
        // Path: A...A (k-1 times) -> R -> A...A (j times) -> R -> ...
        int pos_undershoot = (1 << (k - 1)) - 1;
        for (int j = 0; j < k - 1; j++) {
            int pos_after_backward = (1 << j) - 1;
            int current_steps = (k - 1) + 1 + j + 1 + dp(t - pos_undershoot + pos_after_backward);
            memo[t] = Math.min(memo[t], current_steps);
        }

        return memo[t];
    }
}
```
### Algorithm
- Define a recursive function `dp(t)` that computes the minimum steps to reach position `t`.
- Use a memoization array `memo` to store the results of `dp(t)` to avoid redundant calculations.
- The base case is `dp(0) = 0`.
- For a given `t`, find `k` such that `2^(k-1) <= t < 2^k`.
- Consider the following cases to form the recurrence relation:
  1. **Exact Match:** If `t` is of the form `2^k - 1`, the answer is `k` steps (all 'A's).
  2. **Overshoot:** Go `k` steps forward (`A...A`) to position `2^k - 1`, which is past `t`. This takes `k` steps. Then, reverse ('R', 1 step). The problem reduces to reaching a target of `(2^k - 1) - t`. Total steps: `k + 1 + dp((2^k - 1) - t)`.
  3. **Undershoot and Maneuver:** Go `k-1` steps forward (`A...A`) to position `2^(k-1) - 1`. This takes `k-1` steps. Reverse ('R', 1 step). Go backward `j` steps (`A...A`, `j` steps) to position `(2^(k-1) - 1) - (2^j - 1)`. Reverse again ('R', 1 step). The problem reduces to reaching the remaining distance. Total steps: `(k-1) + 1 + j + 1 + dp(t - (2^(k-1) - 1) + (2^j - 1))`. We minimize this over all possible `j < k-1`.
- The value of `dp(t)` is the minimum of the results from these cases.

# Solutions
### Java

```java
class Solution {
public
  int racecar(int target) {
    int[] dp = new int[target + 1];
    for (int i = 1; i <= target; ++i) {
      int k = 32 - Integer.numberOfLeadingZeros(i);
      if (i == (1 << k) - 1) {
        dp[i] = k;
        continue;
      }
      dp[i] = dp[(1 << k) - 1 - i] + k + 1;
      for (int j = 0; j < k; ++j) {
        dp[i] =
            Math.min(dp[i], dp[i - (1 << (k - 1)) + (1 << j)] + k - 1 + j + 2);
      }
    }
    return dp[target];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int racecar(int target) {
    vector<int> dp(target + 1);
    for (int i = 1; i <= target; ++i) {
      int k = 32 - __builtin_clz(i);
      if (i == (1 << k) - 1) {
        dp[i] = k;
        continue;
      }
      dp[i] = dp[(1 << k) - 1 - i] + k + 1;
      for (int j = 0; j < k; ++j) {
        dp[i] = min(dp[i], dp[i - (1 << (k - 1)) + (1 << j)] + k - 1 + j + 2);
      }
    }
    return dp[target];
  }
};

```

### Python

```python
class Solution:
    def racecar(self, target: int) -> int: dp = [0] * (target + 1) for i in range(1, target + 1): k = i . bit_length() if i == 2 ** k - 1: dp[i] = k continue dp[i] = dp[2 ** k - 1 - i] + k + 1 for j in range(k - 1): dp[i] = min(dp[i], dp[i - (2 ** (k - 1) - 2 ** j)] + k - 1 + j + 2) return dp[target]

```