假设我们有一辆汽车，正在一维道路上行驶。当前，我们处于位置= 0且速度=1。我们可以执行这两个操作中的任何一个。
加速度：位置：=位置+速度和速度：=速度* 2倒档：速度：= -1（当速度> 0时，否则速度：= 1）。
我们必须找到至少达到目标所需的移动次数。
因此，如果输入类似于target = 10，则输出将为7。
为了解决这个问题，我们将遵循以下步骤-
定义一个功能dfs()。这需要数字，费用，排名，否定目标
返回
ans：= ans和tot的最小值
返回
返回
tot：=成本+最大值2 *（pos − 1）和2 *（neg − 1）
如果tot> = ans，则
如果目标等于0，则
步骤：=（2 ^ digit）− 1
如果步骤* 2 <| target |，则
dfs（数字-1，费用，排名，否定目标）
dfs（数字− 1，成本+数字，pos + 1，负数，目标-步骤）
dfs（数字-1，费用+数字* 2，pos + 2，负数，目标-步骤* 2）
dfs（数字− 1，成本+数字，pos，负+ 1，目标+步长）
dfs（数字− 1，成本+数字* 2，pos，负+ 2，目标+步数* 2）
在主要功能中，执行以下操作-
ans：=无限
嗨：= 1
而2 ^ hi <目标，做
嗨：=嗨+ 1
dfs（hi，0，0，0，目标）
返回ans
让我们看下面的实现以更好地理解-
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