title: Find minimum steps required to reach n
body: <p>I am trying to solve a Dynamic programming problem which is as follows but unable to solve it.</p>
  
  <p><em>You are given a primitive calculator that can perform the following three operations with the current number : multiply  by 2, multiply  by 3, or add 1 to . Your goal is given a positive integer , find the minimum number of operations needed to obtain the number  starting from the number 1</em></p>
  
  <p><strong>I found the solution on stackoverflow itself</strong> but unable to understand what's going on.</p>
  
  <p>I have heard that every DP problem can be solved by creating matrix which I was trying to do but don't know where I am going wrong. The table is created below which shows number of steps required to reach to <strong>n</strong> from 1, initially I take values as infinity.</p>
  
  <pre><code>i / j           0           1             2            3                4              5
  plus 1          0           1             2            3                4              5
  multiple by 2   0           infinity      2            infinity         3             infinity
  multiple by 3   0           infinity      infinity     2                infinity      infinity
  </code></pre>
  
  <p>I am trying to solve this problem in Python.
  Can someone please help me.</p>
  
  <p>I found the solution which is as follows but not able to understand exactly what is going on:</p>
  
  <pre><code>import math
  target = int(input())
  
  def optVal(target, cache):
      result = [1] * cache[-1]  # 1
      for i in range(1, cache[-1]): # 2
          result[-i] = target  # 3
          if cache[target-1] == cache[target] - 1:  # 4
              target -= 1
          elif target % 2 == 0 and (cache[target // 2] == cache[target] - 1):  # 5
              target //= 2
          else:  # 6 # target % 3 == 0 and (cache[target // 3] == cache[target] - 1):
              target //= 3
      return result
  
  cache = [0] + [math.inf] * target  # 1
  for i in range(1, len(cache)):  # 2
      temp1 = math.inf
      temp2 = math.inf
      temp3 = math.inf
  
      temp1 = cache[i - 1] + 1
      if i % 2 == 0:
          temp2 = cache[i // 2] + 1
      if i % 3 == 0:
          temp3 = cache[i // 3] + 1
  
      cache[i] = min(temp1, temp2, temp3)
  
  print('Minimum operation: ', cache[target] - 1)
  finalLst = optVal(target, cache)
  print(' '.join([str(x) for x in finalLst]))
  
  Input: 
  5
  Output:
  3
  1245
  </code></pre>