動的プログラミング - プリミティブ計算機Python

Question

この割り当ては、1を加算し、2を掛けて3を掛けることができるプリミティブ計算機への動的プログラミングアプローチを実現することを目的としています。したがって、nの入力では、 n。私は非常に純粋なdpを実装している、あるいは私はdpのアプローチだと思います。それは動作していません。誰にも質問する人はいません。 n = 5の入力に対しては、（[0,1,2,2,3,4]、[1,1,2,3,4,5]）の出力は以下のようになります。リスト番号= [1,2,4,5]または[1,3,4,5]である。助けていただければ幸いです。 elifブロックは本当にifブロックでなければならないこと

def DPmin_operations(n): 

numbers = [] 
minNumOperations = [0]*(n+1) 
numOps = 0 
numbers.append(1) 

for k in range(1,n+1): 
    minNumOperations[k] = 10000 

    # for *3 operator 
    if k % 3 == 0: 
     numOps = minNumOperations[k//3] + 1 
     if numOps < minNumOperations[k]: 
      minNumOperations[k] = numOps 
      numbers.append(k) 
    # for *2 operator 
    elif k % 2 == 0: 
     numOps = minNumOperations[k//2] + 1 
     if numOps < minNumOperations[k]: 
      minNumOperations[k] = numOps 
      numbers.append(k) 
    # for + 1 operator 
    elif k >= 1: 
     numOps = minNumOperations[k - 1] + 1 
     if numOps < minNumOperations[k]: 
      minNumOperations[k] = numOps 
      numbers.append(k) 

return (minNumOperations, numbers) 

Answer 1

注意。現在、あなたは3で割り切ろうとする貪欲なアルゴリズムを使用しています。それが失敗した場合は、2で除算しようとします。それが失敗した場合は1を減算します。3つのオプションがすべて可能なように、6で割り切れる可能性があります。さらに2で割ると3で割ると最適です。

数字のリストを取得するには、最後にそれをしてください。すべての可能な両親を保管し、あなたの目標から後方に向かってどのようにそこに行ったのかを確認してください。

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])