Problem summary

You start at position 0 with speed 1. You can issue two instructions:

• A (accelerate): position += speed; speed *= 2
• R (reverse): if speed > 0 then speed = -1 else speed = 1

Given a target position (positive integer), return the minimum length of an instruction sequence that reaches exactly that target.

Examples
Input: target = 3
Output: 2
Explanation: AA (after two A: position 3)

Input: target = 6
Output: 5
One optimal sequence: AAARA — after AAA position is 7 (overshoot), then R (reverse) and A to move back to 6.

Constraints
target is a positive integer (up to around 10^4 or more in general). The expected solution is not brute force; known optimal approaches use BFS or dynamic programming with recursion + memoization.

Intuition and approach in simple English

The race-car state space (position, speed) can be explored with BFS, but that can be heavy if not bounded carefully. A more elegant and faster approach uses recursion + memoization based on the binary nature of accelerating:

• After n consecutive A instructions (i.e., A repeated n times), the car reaches position 2^n - 1 and speed 2^n.
• For a given target, find the smallest n such that 2^n - 1 >= target. There are two main possibilities:

1. 2^n - 1 == target
   If this holds, the answer is n (just A repeated n times).
2. 2^n - 1 > target (we overshoot if we do n As)
   You have two kinds of strategies:
   • Overshoot and come back: do n As to reach 2^n - 1, then R (1 op) to reverse, then solve the remaining distance (2^n - 1) - target recursively. Total operations: n + 1 + dp((2^n - 1) - target).
   • Stop short, reverse, backtrack some, reverse again, then go forward to finish: for some m with 0 <= m < n:
     • Do n-1 As to reach 2^{n-1} - 1
     • R (reverse), then do m As (moving backwards), then R again to face forward, then solve the remaining forward distance recursively.
     • After n-1 As position = 2^{n-1} - 1. After reversing and doing m As (with negative speed), position becomes 2^{n-1} - 1 - (2^m - 1).
     • Remaining = target - (2^{n-1} - 1 - (2^m - 1)) = target - (2^{n-1} - 1) + (2^m - 1).
     • Total ops = (n-1) + 1 + m + 1 + dp(remaining) = n + m + 1 + dp(remaining).

Take the minimum over the overshoot strategy and all these stop-short strategies. Use memoization to avoid recomputation.

This recursion captures the optimal structure because the accelerate instruction grows position exponentially and optimal sequences often use these full-accelerate chunks.

Algorithm outline (top-down DP with memo)

1. If target == 0, return 0.
2. Compute n = ceil(log2(target + 1)).
3. If 2^n - 1 == target, return n.
4. Initialize answer as overshoot case: ans = n + 1 + dp((2^n - 1) - target).
5. For m from 0 to n-1:
   • remaining = target - (2^{n-1} - 1) + (2^m - 1)
   • candidate = n + m + 1 + dp(remaining)
   • ans = min(ans, candidate)
6. Memoize and return ans.

Time complexity: Each recursive dp(target) will loop up to n times where n ~ log(target). With memoization, the number of distinct targets seen is limited; overall complexity is roughly exponential in log(target) (polynomial in log target), usually very fast for constraints up to typical LeetCode targets.

Java implementation (top-down memoization)

import java.util.HashMap;
import java.util.Map;

public class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();

    public int racecar(int target) {
        return dp(target);
    }

    private int dp(int target) {
        if (target == 0) return 0;
        if (memo.containsKey(target)) return memo.get(target);

        // find smallest n such that 2^n - 1 >= target
        int n = 1;
        while ((1 << n) - 1 < target) {
            n++;
        }

        // if exact match: n A's
        if ((1 << n) - 1 == target) {
            memo.put(target, n);
            return n;
        }

        // option 1: overshoot with n A's, then R, then solve remainder
        int overshootDistance = (1 << n) - 1 - target;
        int best = n + 1 + dp(overshootDistance);

        // option 2: try stopping earlier, reversing, make some moves, reverse again, then finish
        // try m = 0..n-1 where we do (n-1) A's, R, m A's, R, then dp(remaining)
        for (int m = 0; m < n; m++) {
            int forwardUntil = (1 << (n - 1)) - 1; // position after n-1 As
            int backDistance = (1 << m) - 1;      // distance covered after m As (in opposite direction)
            int remaining = target - (forwardUntil - backDistance);
            // ops: (n-1) As + 1 R + m As + 1 R + dp(remaining)
            int candidate = (n - 1) + 1 + m + 1 + dp(remaining);
            if (candidate < best) best = candidate;
        }

        memo.put(target, best);
        return best;
    }

    // For quick manual testing
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.racecar(3)); // expected 2
        System.out.println(s.racecar(6)); // expected 5
        System.out.println(s.racecar(1)); // expected 1
        System.out.println(s.racecar(4)); // common test
    }
}

Notes about the code

• 1 << n computes 2^n (works while n is small enough; for typical constraints this is safe). If target may be very large (beyond 2^30), use long shifts or Math.pow.
• We use a HashMap<Integer, Integer> for memoization. This ensures repeated subproblems are answered in O(1).
• The for (m = 0; m < n; m++) tries the strategy of stopping short and making a controlled backtrack — it is necessary to find some optimal sequences.

Dry run (two examples)

Example 1: target = 3

• Find n such that 2^n - 1 >= 3. n = 2 gives 2^2 - 1 = 3, exact match.
• Return n = 2. Sequence: AA.

Example 2: target = 6

• n = 3 because 2^3 - 1 = 7 >= 6 and 7 != 6.
• Overshoot option: do AAA (3 ops) reach 7, then R (1 op), remaining = 7 - 6 = 1. So cost = 3 + 1 + dp(1). dp(1) = 1 (single A). Total = 5.
• Try stopping-short options (m from 0 to 2):
  • m = 0: forwardUntil = 2^(3-1)-1 = 3; backDistance = 0; remaining = 6 - (3 - 0) = 3; cost = (3-1)+1+0+1 + dp(3) = 2+1+0+1 + 2 = 6
  • m = 1: forwardUntil = 3; backDistance = 1; remaining = 6 - (3 - 1) = 4; cost = 2+1+1+1 + dp(4) = 5 + dp(4) (dp(4) >= 2 so candidate >= 7)
  • m = 2: forwardUntil = 3; backDistance = 3; remaining = 6 - (3 - 3) = 6; cost = 2+1+2+1 + dp(6) = 6 + dp(6) (recursive)
• The overshoot path gives best = 5, which is optimal. One concrete instruction sequence is A A A R A -> positions 1,3,7, then reverse and step to 6.

Complexity and final notes

• Each DP call loops up to n ≈ log2(target) times, and memoization reduces repeated work. In practice the approach runs quickly for typical target sizes.
• Alternative approach: BFS on (position, speed) states with pruning. BFS is intuitive (shortest sequence) but you must bound position and avoid infinite exploration; DP approach leverages structure and is usually faster.
• Edge cases: small targets (1,2,3) are handled quickly by the 2^n - 1 checks; memo avoids recomputation for sub-targets.