สมมุติว่าเรามีรถและกำลังขับมันบนถนนมิติเดียว ขณะนี้เราอยู่ที่ตำแหน่ง =0 และด้วยความเร็ว =1 เราสามารถดำเนินการใดก็ได้ในสองการดำเนินการนี้
-
อัตราเร่ง:ตำแหน่ง :=ตำแหน่ง + ความเร็วและความเร็ว :=ความเร็ว * 2 เกียร์ถอยหลัง:ความเร็ว :=-1 เมื่อความเร็ว> 0 มิฉะนั้น ความเร็ว :=1.
เราต้องหาจำนวนการเคลื่อนไหวที่จำเป็นอย่างน้อยเพื่อให้บรรลุเป้าหมาย
ดังนั้น หากอินพุตเหมือนเป้าหมาย =10 ผลลัพธ์จะเป็น 7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน dfs() จะใช้ตัวเลข, ต้นทุน, ตำแหน่ง, เชิงลบ, เป้าหมาย
-
tot :=ราคา + สูงสุด 2 *(pos − 1) และ 2 * (neg − 1)
-
ถ้า tot>=ans แล้ว
-
กลับ
-
-
ถ้าเป้าหมายเท่ากับ 0 แล้ว
-
ans :=ขั้นต่ำของ ans และ tot
-
กลับ
-
-
ขั้นตอน :=(2^หลัก) − 1
-
ถ้าขั้นตอน * 2 <|target| แล้ว
-
กลับ
-
-
dfs(ตัวเลข − 1, ราคา, ตำแหน่ง, ลบ, เป้าหมาย)
-
dfs(หลัก − 1, ราคา + หลัก, pos + 1, ลบ, เป้าหมาย − ขั้นตอน)
-
dfs(หลัก − 1, ราคา + หลัก * 2, pos + 2, neg, เป้าหมาย − ขั้นตอน * 2)
-
dfs(หลัก − 1, ราคา + หลัก, pos, ลบ + 1, เป้าหมาย + ขั้นตอน)
-
dfs(หลัก − 1, ราคา + หลัก * 2, pos, ลบ + 2, เป้าหมาย + ขั้นตอน * 2)
-
-
จากหน้าที่หลัก ให้ทำดังต่อไปนี้ -
-
ตอบ :=อนันต์
-
สวัสดี :=1
-
ในขณะที่ 2^hi <เป้าหมาย ทำ
-
สวัสดี :=สวัสดี + 1
-
-
dfs(สวัสดี 0, 0, 0, เป้าหมาย)
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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))
อินพุต
10
ผลลัพธ์
7
