Giả sử, chúng ta có một chiếc ô tô và đang lái nó trên đường một chiều. Hiện tại, chúng tôi đang ở vị trí =0 và với tốc độ =1. Chúng tôi có thể thực hiện bất kỳ hoạt động nào trong hai thao tác này.
-
Gia tốc:vị trí:=vị trí + tốc độ và tốc độ:=tốc độ * 2 Số lùi:tốc độ:=−1 khi tốc độ> 0 nếu không tốc độ:=1.
Chúng ta phải tìm ra số lần di chuyển cần thiết ít nhất để đạt được mục tiêu.
Vì vậy, nếu đầu vào là target =10, thì đầu ra sẽ là 7.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm dfs (). Điều này sẽ lấy chữ số, chi phí, vị trí, phủ định, mục tiêu
-
tổng:=chi phí + tối đa là 2 * (pos - 1) và 2 * (neg - 1)
-
nếu tot> =ans, thì
-
trở lại
-
-
nếu mục tiêu giống 0, thì
-
ans:=tối thiểu ans và tổng
-
trở lại
-
-
bước:=(2 ^ chữ số) - 1
-
nếu bước * 2 <| target |, thì
-
trở lại
-
-
dfs (chữ số - 1, chi phí, pos, neg, target)
-
dfs (chữ số - 1, chi phí + chữ số, vị trí + 1, phủ định, mục tiêu - bước)
-
dfs (chữ số - 1, chi phí + chữ số * 2, pos + 2, phủ định, mục tiêu - bước * 2)
-
dfs (chữ số - 1, chi phí + chữ số, vị trí, phủ định + 1, mục tiêu + bước)
-
dfs (chữ số - 1, chi phí + chữ số * 2, pos, neg + 2, target + step * 2)
-
-
Từ chức năng chính, thực hiện như sau -
-
ans:=infinity
-
chào:=1
-
trong khi 2 ^ xin chào
-
chào:=chào + 1
-
-
dfs (chào, 0, 0, 0, target)
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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