在Python中找出达到终点所需的移动次数的程序

假设我们有一辆车，正在一维道路上行驶。目前我们的位置是0，速度为1。我们可以执行任何两个操作中的任何一个。

• 加速：位置：=位置+速度，速度：=速度*2 倒挡：速度：=−1（当速度＞0时），否则速度：= 1。

我们必须找出到达目标所需的最少移动次数。

因此，如果输入为target = 10，则输出将为7。

要解决此问题，我们将遵循以下步骤-

• 定义一个函数dfs()。这将取代数字、成本、pos、neg、目标

只要完成步骤1~9，无论结果如何，都会返回结果，然后再去执行步骤10~13。
* tot：=成本+2*（pos-1）和2 *（neg-1）的最大值。

• 如果tot≥ans，那么
  • 返回
• 如果目标与0相同，则
  • ans：=最小值ans和tot

  • 返回

• 步骤：=（2^digit）- 1

• 如果步骤*2<|target|，则

  • 返回
• dfs(digit-1,cost,pos,neg,target)

• dfs(digit-1,cost+digit,pos+1,neg,target-step)

• dfs(digit-1,cost+digit2,pos+2,neg,target-step2)

• dfs(digit-1,cost+digit,pos,neg+1,target+step)

• dfs(digit-1,cost+digit2,pos,neg+2,target+step2)

  • 从主函数中执行以下操作-

  • ans：=无限大

  • hi：=1

  • while 2^hi<target， do

  • hi：=hi+1

  • dfs(hi,0,0,0,target)

  • 返回ans

让我们看以下实现以更好的理解-

更多Python相关文章，请阅读：Python 教程

示例

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