title: Dynamic Programming - Primitive Calculator
body: <p>I am trying to solve the following problem using dynamic programming. </p>
  
  <p>You are given a primitive calculator that can perform the following three operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x. Your goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.
  The output should contain two parts - the number of minimum operations, and the sequence to get to n from 1. </p>
  
  <p>I found the following solution from this post: <a href="https://stackoverflow.com/questions/37561224/dynamic-programming-primitive-calculator-python">Dynamic Programming - Primitive Calculator Python</a>.</p>
  
  <p>I am having problem understanding the back tracing part, starting from
      "numbers = [ ]
      k = n"
  Could anyone explain the logic behind it? It works like magic...</p>
  
  <p>The code is as follows:</p>
  
  <pre><code>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 &lt; 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 &lt; 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 &gt; 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])
  </code></pre>