動態規劃 - 原始計算器

-2

給出一個原始計算器，它可以用當前數字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])

來源

2017-12-18 Tian Park

瞭解發生什麼的方法是使用調試器。在'numbers = []'處放置一個斷點，然後在循環中單步執行。每次查看'numbers'的內容，並檢查'all_parents'數組。你有所有需要理解的工具。你只需要花一點時間就可以使用它們。 –

提示：要找到最短的操作達到數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。

來源

2017-12-18 11:17:46 DSinghvi

動態規劃 - 原始計算器

回答

相關問題