• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

动态规划 – 原始计算器

python 来源:Tian Park 9次浏览

我想用动态规划解决以下问题。动态规划 – 原始计算器

给出一个原始计算器,它可以用当前数字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。


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)