Leetcode: 818. Race Car

Mistake: Bug caused by incorrect assumption. Started to look for prunes and added one to avoid numbers greater than target.
Mistake: Failed to consider different strategies to solve the problem. Came up with Breadth-first search and didn't ask myself if I could solve the problem using Dynamic Programming.
Mistake: Missing inspection of test cases. The test case 5 gave a hint which I didn't see because I rushed to code the BFS.

Can we simplify the problem while keeping it the same? As in Leetcode: 1675. Minimize Deviation in Array, we can reduce the number of different operations by thinking on the problem to get from \(0\) to \(i\) only doing forward moves. \(dp[i]\) is the number of steps to get from \(0\) to \(i\) starting with speed 1. The best way to get close to \(i\) is to accelerate as much as possible. Be \(j\) the closest position to \(i\) that we can get accelerating \(t\) times at speed \(s\). If \(i=j\), the solution is \(dp[i]=t\). Otherwise, \(j

class Solution:
    def racecar(self, target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 0

        def stops(target):
            pos = 0
            speed = 1
            steps = 0
            yield (pos, speed, steps)
            while pos + speed <= i:
                pos += speed
                speed *= 2
                steps += 1
                yield (pos, speed, steps)


        for i in range(1, target + 1):
            *_, (pos, speed, steps) = stops(i)
            if pos == i:
                dp[i] = steps
                continue

            dp[i] = steps + 1 + dp[(pos + speed) - i] + 1
            for rpos, _, rsteps in stops(pos):
                dp[i] = min(dp[i], steps + 1 + rsteps + 1 + dp[i - (pos - rpos)])

        return dp[target]

assert Solution().racecar(3) == 2
assert Solution().racecar(6) == 5

Breadth-first search solution starts by doing as much A as possible and them searching for the optimal path:

class Solution:
    def racecar(self, target: int) -> int:
        seen = set()

        pos = 0
        speed = 1
        steps = 0
        while pos + speed <= target:
            pos += speed
            speed *= 2
            steps += 1

        queue = [(pos, speed, steps)]
        for pos, speed, steps in queue:
            if pos == target:
                return steps

            if (pos, speed) in seen:
                continue
            seen.add((pos, speed))

            queue.append((pos + speed, speed * 2, steps + 1))
            if speed > 0:
                queue.append((pos, -1, steps + 1))
            else:
                queue.append((pos, +1, steps + 1))


assert Solution().racecar(3) == 2
assert Solution().racecar(6) == 5