title: Dynamic Programming - Primitive Calculator Python
body: <p>This assignment aims to implement a dynamic programming approach to a primitive calculator that can only add 1, multiply by 2 and multiply by 3. So with an input of n determine the minimum number of operations to reach n. I've implemented a very naive dp or what I think is a dp approach. It is not working. I have no-one else to ask. For an input of n = 5 the output of the below is: ([0, 1, 2, 2, 3, 4], [1, 1, 2, 3, 4, 5]) whereas there are two correct outputs for the list numbers = [1, 2, 4, 5] or [1, 3, 4, 5]. Some help would be greatly appreciated.</p>
  
  <pre><code>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 &lt; minNumOperations[k]:
              minNumOperations[k] = numOps
              numbers.append(k)
      # for *2 operator
      elif k % 2 == 0:
          numOps = minNumOperations[k//2] + 1
          if numOps &lt; minNumOperations[k]:
              minNumOperations[k] = numOps
              numbers.append(k)
      # for + 1 operator 
      elif k &gt;= 1:
          numOps = minNumOperations[k - 1] + 1
          if numOps &lt; minNumOperations[k]:
              minNumOperations[k] = numOps
              numbers.append(k)
  
  return (minNumOperations, numbers)
  </code></pre>