原始計算器的動態編程

Question

我正在處理的問題，這是非常類似於更改硬幣的問題。

我需要實現一個簡單的計算器，它可以用當前數字x執行以下三個操作：乘以x乘以2，乘以x乘以3或給x加1。

目標被賦予一個正整數n，發現以獲得從1

我製成的貪婪方法，該編號開始的數量n所需的操作的最小數量，伯爾它顯示不正確的結果

import sys 

def optimal_sequence(n): 
    sequence = [] 
    while n >= 1: 
     sequence.append(n) 
     if n % 3 == 0: 
      n = n // 3 
     elif n % 2 == 0: 
      n = n // 2 
     else: 
      n = n - 1 
    return reversed(sequence) 

input = sys.stdin.read() 
n = int(input) 
sequence = list(optimal_sequence(n)) 
print(len(sequence) - 1) 
for x in sequence: 
    print(x) 

例如：

Input: 10 
Output: 
4 
1 2 4 5 10 

4步驟。但正確的是3步：

Output: 
3 
1 3 9 10 

我讀了關於動態編程，並希望我能在這裏實現它。但是，在特定情況下我無法正確使用它，有人可以給我一個建議嗎？

Answer 1

只需用簡單的遞歸和Memoization解決它：

代碼：

d = {} 

def f(n): 
    if n == 1: 
     return 1, -1 
    if d.get(n) is not None: 
     return d[n] 
    ans = (f(n - 1)[0] + 1, n - 1) 

    if n % 2 == 0: 
     ret = f(n // 2) 
     if ans[0] > ret[0]: 
      ans = (ret[0] + 1, n // 2) 

    if n % 3 == 0: 
     ret = f(n // 3) 
     if ans[0] > ret[0]: 
      ans = (ret[0] + 1, n // 3) 

    d[n] = ans 
    return ans 

def print_solution(n): 
    if f(n)[1] != -1: 
     print_solution(f(n)[1]) 
    print n, 

def solve(n): 
    print f(n)[0] 
    print_solution(n) 
    print '' 

solve(10) 

提示：F（X）返回一個元組（A，B），其a表示最小步驟獲得x從1開始，並且b表示獲得最佳解決方案的前一個數字。 b僅用於打印解決方案。

輸出：

4 # solution for 10 
1 3 9 10 

7 # solution for 111 
1 2 4 12 36 37 111 

您可以調試我的代碼，並瞭解它是如何工作的。如果你是DP的初學者，你可以閱讀我的另一個關於DP的SO post以快速入門。

---

因爲Python不能遞歸很多（約10000），我寫一個迭代版本：

# only modified function print_solution(n) and solve(n) 

def print_solution(n): 
    ans = [] 
    while f(n)[1] != -1: 
     ans.append(n) 
     n = f(n)[1] 
    ans.append(1) 
    ans.reverse() 
    for x in ans: 
     print x, 

def solve(n): 
    for i in range(1, n): 
     f(i)[0] 
    print_solution(n) 
    print '' 

solve(96234) # 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234