动态规划 - 原始计算器

  • Z时代
  • 2024-01-10
  • 分类：问答

我想用动态规划" title="动态规划">动态规划解决以下问题。动态规划 - 原始计算器

给出一个原始计算器，它可以用当前数字x执行以下三个操作：乘以x乘以2，乘以x乘以3或给x加1。你的目标是给出一个正整数n，找到从数字1开始获得数字n所需的最小操作次数。 输出应该包含两部分 - 最小操作的数量和从1到n的序列。

我从这篇文章中发现了以下解决方案：Dynamic Programming - Primitive Calculator Python。

我有问题理解反向跟踪部分，从起始 “号码= [] K = N” 任何人都可以解释其背后的逻辑？它的工作原理像变魔术一样......

的代码如下：

def dp_min_ops(n): 
    all_parents = [None] * (n + 1) 
    all_min_ops = [0] + [None] * n 
    for k in range(1, n + 1): 
     curr_parent = k - 1 
     curr_min_ops = all_min_ops[curr_parent] + 1 
     if k % 3 == 0: 
      parent = k // 3 
      num_ops = all_min_ops[parent] + 1 
      if num_ops < curr_min_ops: 
       curr_parent, curr_min_ops = parent, num_ops 
     if k % 2 == 0: 
      parent = k // 2 
      num_ops = all_min_ops[parent] + 1 
      if num_ops < curr_min_ops: 
       curr_parent, curr_min_ops = parent, num_ops 
     all_parents[k], all_min_ops[k] = curr_parent, curr_min_ops 
    numbers = [] 
    k = n 
    while k > 0: 
     numbers.append(k) 
     k = all_parents[k] 
    numbers.reverse() 
    return all_min_ops, numbers 
print(dp_min_ops(5)) # ([0, 1, 2, 2, 3, 4], [1, 3, 4, 5]) 
print(dp_min_ops(10)) # ([0, 1, 2, 2, 3, 4, 3, 4, 4, 3, 4], [1, 3, 9, 10])

回答：

提示：要找到最短的操作达到数n。您将需要如下回答：

1）min_operations[n-1]

2）如果（n是被2整除）

  min_operations[n/2]

3）如果（n是被3整除）

  min_operations[n/3]

现在，如果我们发现上述三个操作中的最小值，我们将通过将这三个操作中的最小值（如果有效）加1来达到最小操作次数。

现在您知道达到1的操作的最小数量为零。所以现在开始计算从1到n的最小操作次数。因为每当你计算任何数字时，你总会对所有小于k的数字回答ie ie。 k-1，k/2（如果可分割），k/3（如果可分割）。因此，如果你从1到n遍历所有数字，你可以计算n。

以上是 动态规划 - 原始计算器 的全部内容， 来源链接： utcz.com/qa/260784.html

回到顶部