假设我们有一辆汽车,正在一维道路上行驶。当前,我们处于位置= 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