title: Coin change porblem: difference between these two methods
body: <p>I am implementing the coin change problem in python in CS50's pset6. When I first tackled the problem, this was the algorithm I used:</p>
  
  <pre><code>import time
  
  while True:
      try:
          totalChange = input('How much change do I owe you? ')
          totalChange = float(totalChange)  # check it it's a valid numeric value
          if totalChange &lt; 0:
              print('Error: Please enter a positive numeric value')
              continue
          break
      except:
          print('Error: Please enter a positive numeric value')
  start_time1 = time.time()
  change1 = int(totalChange * 100)  # convert money into cents
  n = 0
  while change1 &gt;= 25:
      change1 -= 25
      n += 1
  while change1 &gt;= 10:
      change1 -= 10
      n += 1
  while change1 &gt;= 5:
      change1 -= 5
      n += 1
  while change1 &gt;= 1:
      change1 -= 1
      n += 1
  
  print(f'Method1: {n}')
  
  print("--- %s seconds ---" % (time.time() - start_time1))
  </code></pre>
  
  <p>Having watched the lecture on dynamic programming, I wanted to implement it into this problem. This was my attempt:</p>
  
  <pre><code>while True:
      try:
          totalChange = input('How much change do I owe you? ')
          totalChange = float(totalChange)  # check it it's a valid numeric value
          if totalChange &lt; 0:
              print('Error: Please enter a positive numeric value')
              continue
          break
      except:
          print('Error: Please enter a positive numeric value')
  start_time2 = time.time()
  
  change2 = int(totalChange*100)
  rowsCoins = [1,5,10,25]
  colsCoins = list(range(change2 + 1))
  n = len(rowsCoins)
  m = len(colsCoins)
  matrix = [[i for i in range(m)] for j in range(n)]
  
  for i in range(1,n):
      for j in range(1,m):
          if rowsCoins[i] == j:
              matrix[i][j] = 1
          elif rowsCoins[i] &gt; j:
              matrix[i][j] = matrix[i-1][j]
          else:
              matrix[i][j] = min(matrix[i-1][j], 1 + matrix[i][j-rowsCoins[i]])
  
  print(f'Method2: {matrix[-1][-1]}')
  
  print("--- %s seconds ---" % (time.time() - start_time2))
  </code></pre>
  
  <p>When I run the program, it gives the correct answers, but it takes a much longer time.</p>
  
  <ol>
  <li>How could I adjust the second code so that it is correctly implementing dynamic programming. Is my problem that I am starting the loops from the top left corner of the matrix instead of the bottom right?</li>
  <li>What are the time complexities of the algorithms for each code that I wrote (as well as for a correct implementation of dynamic programming). I suspect that for the first code, it follows O(n^4), and for the second code O(n*m), and a correct implementation of dynamic programming should be O(n). Am I correct to think this?</li>
  </ol>
  
  <p>Any help for a better understanding of these algorithms is much appreciated. Thanks in advance.</p>