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.
Dynamic Programming with breadth-first search
class Solution:
def racecar(self, target: int) -> int:
dist = {(0, 1): 0}
from collections import deque
dq = deque([(0, 1)])
while dq:
pos, speed = dq.popleft()
if pos == target:
return dist[(pos, speed)]
neighbors = [(pos, -speed // abs(speed)), (pos + speed, 2 * speed)]
for nei in neighbors:
if nei not in dist:
dq.append(nei)
dist[nei] = dist[(pos, speed)] + 1
Dynamic Programming combined with Greedy (Time O(TlogT), Space O(T))
class Solution:
@cache
def racecar(self, target: int) -> int:
n = target.bit_length()
# Just use consecutive A and you will get there
if (target + 1) & target == 0: # This is the binary trick to see if target + 1 is a power of 2
return n
# Go past the target, then come back.
result = self.racecar(2 ** n - 1 - target) + n + 1 # The "n" mean first use n consecutive A, then "1" means use 1 R
# Go as long as you do not pass the target. Then come back several steps. Then go ahead.
for m in range(n - 1):
result = min(result, + self.racecar(target - (2 ** (n - 1) - 2 ** m)) + n - 1 + 1 + m + 1) # The "n - 1" means first use (n - 1) A, then use 1 R, then use m A, m will be smaller than n - 1, then use 1 R
return result