我在CS50的pset6中用python实现了硬币兑换问题，当我第一次处理这个问题时，我使用的算法是：

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 < 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 >= 25:
    change1 -= 25
    n += 1
while change1 >= 10:
    change1 -= 10
    n += 1
while change1 >= 5:
    change1 -= 5
    n += 1
while change1 >= 1:
    change1 -= 1
    n += 1

print(f'Method1: {n}')

print("--- %s seconds ---" % (time.time() - start_time1))

看了动态规划的讲座后，我想把它实现到这个问题上。这是我的尝试：

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 < 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] > 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))

当我运行程序时，它给出了正确的答案，但需要的时间要长得多。
1.我该如何调整第二段代码，使其正确地实现动态编程？我的问题是从矩阵的左上角而不是右下角开始循环吗？
1.对于我写的每一段代码（以及动态编程的正确实现），算法的时间复杂度是多少？我猜想对于第一段代码，它遵循O（n^4），对于第二段代码，它遵循O（n*m），而动态编程的正确实现应该是O（n），我这样想对吗？
任何有助于更好地理解这些算法的帮助都是非常感谢的。