動的プログラミング - プリミティブ電卓

Question

私は動的プログラミングを使用して次の問題を解決しようとしています。

現在の数値xを使って次の3つの演算を実行できます.xを2倍、xを3倍、xを1に加えます。あなたの目標には正の整数nが与えられ、数字1から始まる数字nを得るために必要な演算の最小数を見つけます。 出力には、最小演算の数と1からnになるシーケンスの2つの部分

私はこの記事から次の解決策を見つけました：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]) 

Answer 1

ヒントは：番号nに到達するために最低限の操作を確認するには、次のように

コードがある...魔法のように動作します。あなたは、次の答えが必要になります。

1）min_operations[n-1]

2）（nは3で割り切れる）

  min_operations[n/3] 

場合（nは2で割り切れる）

  min_operations[n/2] 

3）場合

これらの3つの操作の最小値を見つけたら、これらの3つのうちの最小値に1を加えることによって、nに達する操作の最小数を得ます（有効な場合）。

ここで、1に達する操作の最小数はゼロであることがわかりました。今度は、1からnまでの最小操作数の計算を開始します。任意の数を計算するたびにkと言うと、kより小さいすべての数に対して常に答えが得られるからです。 k-1、k/2（割り切れる場合）、k/3（割り切れる場合）。したがって、1からnまでの間にあるすべての数の答えを見つけることができれば、nを計算することができます。