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`


def racecar(target: int) -> int:
    memo = {}

    def dp(position, speed):
        if abs(position) > 2 * target:
            return target + 1
        if position == target:
            return 0 if speed == 1 else 1
        if (position, speed) in memo:
            return memo[(position, speed)]

        ans = dp(position + speed // 2, -speed // 2) + 1 if speed > 0 else dp(position - speed // 2, -speed // 2) + 1
        ans = min(ans, dp(position + speed, speed * 2) + 1)
        memo[(position, speed)] = ans
        return ans

    return dp(0, 1)
