Race Car Python Solution with Tests

lcpy gen -n 818   # by problem number
lcpy gen -s race_car   # by problem name

Input: target = 3
Output: 2

Input: target = 6
Output: 5

class Solution:
    # Time: O(target * log(target))
    # Space: O(target)
    def racecar(self, target: int) -> int:
        dp = [0] * (target + 1)
        for t in range(1, target + 1):
            k = t.bit_length()
            if t == 2**k - 1:
                dp[t] = k
                continue
            best = k + 1 + dp[2**k - 1 - t]
            for j in range(k - 1):
                nxt = t - 2 ** (k - 1) + 2**j
                best = min(best, k + j + 1 + dp[nxt])
            dp[t] = best
        return dp[target]