Untitled

class Solution:
    def racecar(self, target: int) -> int:
        n = target.bit_length()
        if (target == 2**n - 1):
            return n

        dp = [float('inf')]*(target+1)
        dp[0] = 0
        dp[1] = 1

        for i in range(2, target+1):
            k = i.bit_length()
            if i == 2**k - 1:
                dp[i] = k
                continue

            for j in range(k-1):
                dp[i] = min(dp[i], dp[i - (2**(k-1)) + 2**j] + k-1+j+2)
            
            dp[i] = min(dp[i], dp[2**k-i-1] + k+1)

        return dp[target]