รถอยู่ที่ตำแหน่ง 0 ความเร็ว 1 ทำได้ 2 การกระทำ: เร่ง (position += speed, speed *= 2) หรือ เลี้ยวกลับ (speed = -1 ถ้า speed>0 ไม่อย่างนั้น speed=1) หาจำนวนการกระทำน้อยที่สุดเพื่อถึง target
ตัวอย่าง: target=10 → 7 ครั้ง
อัลกอริธึม DFS + Pruning
- คำนวณ
hiเป็นกำลังสองที่มากกว่า target - DFS ลองทุกกรณี: ไม่ทำอะไร, เร่ง 1 ครั้ง, เร่ง 2 ครั้ง, เลี้ยวกลับ 1 ครั้ง, เลี้ยวกลับ 2 ครั้ง
- ตัดกิ่งที่ cost เกินค่าที่ดีที่สุดแล้ว
การนำไปใช้
class Solution:
def solve(self, target):
self.ans = int(1e9)
hi = 1
while (1 << hi) < target:
hi += 1
self.dfs(hi, 0, 0, 0, target)
return self.ans
def dfs(self, digit, cost, pos, neg, target):
tot = cost + max(2 * (pos - 1), 2 * neg - 1)
if tot >= self.ans:
return
if target == 0:
self.ans = min(self.ans, tot)
return
step = (1 << digit) - 1
if step * 2 < abs(target):
return
self.dfs(digit - 1, cost, pos, neg, target)
self.dfs(digit - 1, cost + digit, pos + 1, neg, target - step)
self.dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)
self.dfs(digit - 1, cost + digit, pos, neg + 1, target + step)
self.dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)
ob = Solution()
print(ob.solve(10)) # 7
