https://leetcode.com/problems/race-car/

Python3

Кажется, все идеально, если двигаться так: R только когда уезжаем от цели или когда следующим шагом пересечем ее.

class Solution:
    def racecar(self, target: int) -> int:
        from collections import deque
 
        q = deque([(0, 0, 1)]) # length, position, speed
        best = float('inf')
        while q:
            length, position, speed = q.popleft()
            if position == target:
                best = min(best, length)
            if length >= best:
                continue
            # A
            q.append((length + 1, position + speed, 2 * speed))
 
            if (position + speed > target and speed > 0) or (position + speed < target and speed < 0):
                # R
                q.append((length + 1, position, (-1) * speed / abs(speed)))
        return best