找出在Python中到达终点的移动次数的程序
假设我们有一辆汽车，正在一维道路上行驶。当前，我们处于位置=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