blob: 5352fbe9d6ebdc58a2be2273af64a5f1a74d7144 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# 818. Race Car
"""
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). given a
target position 'target', return the length of the shortest sequence of
instructions to get there.
"""
class Solution(object):
dp = {0: 0}
def racecar(self, target):
"""
:type target: int
:rtype: int
"""
if target in self.dp:
return self.dp[target]
n = target.bit_length()
if 2**n - 1 == target:
self.dp[target] = n
else:
self.dp[target] = self.racecar(2**n - 1 - target) + n + 1
for m in range(n - 1):
self.dp[target] = min(
self.dp[target],
self.racecar(target - 2 ** (n - 1) + 2**m) + n + m + 1,
)
return self.dp[target]
if __name__ == "__main__":
obj = Solution()
print(obj.racecar(3))
print(obj.racecar(6))
|