Leetcode: 818 race car

Description

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.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example

Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.

Note

1 <= target <= 10000.

分析

从题意中可以看出，到达 位置 2^n -1 需要 n 步。到达 非 2^n -1 位置的都至少需要一次 掉头操作。 可能是在 2^(n+1) -1 、2^n  -2^x （n >x） 处掉头 

code

import math 


class Solution:
    def racecar(self, target: int) -> int:
        dp = {}
        def getnum(t):
            if t in dp:
                return dp[t]

            exp = int(math.log2(t))+1
            if t > (1 << exp) -1:
                exp += 1
            if (1 << exp) == t+1:
                dp[t] = exp
                return dp[t]
      
            dp[t] = exp + getnum((1 << exp)-1- t) + 1
            vv = t - (1 << (exp-1)) 

            for ne in range(exp-1):
                s = (1 << ne) 
                dp[t] = min(dp[t], exp + 1 +ne +  getnum(vv+s))

            return dp[t]
        getnum(target)
        return dp[target]

总结

Runtime: 48 ms, faster than 87.70% of Python3 online submissions for Race Car.
Memory Usage: 13.9 MB, less than 83.28% of Python3 online submissions for Race Car.