Chương trình tìm số bước di chuyển đến đích trong Python

Xe chạy trên đường 1 chiều. Vị trí bắt đầu = 0, tốc độ = 1. Hai thao tác: Gia tốc (position += speed, speed *= 2) hoặc Số đảo (speed = -1 nếu speed > 0 else 1). Tìm số bước tối thiểu để đến target.

Ví dụ target = 10 -> 7 bước.

Giải bằng DFS với cắt tỉa: tham số digit (lũy thừa 2), cost, pos, neg, target còn lại.

Ví dụ

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))

Đầu vào

10

Đầu ra

7