Coin change problem in Python (Greedy and DP)

coinsChange.py

def greedyCoinsChange(A, C):
    C.sort(reverse = True)
    counter = 0
    for c in C:
        if (A > 0):
            counter = counter + (A // c)
            A = A % c
        else:
            break
    return counter

import sys
INF = sys.maxsize

def dpCoinsChange(A, C):
    C.sort(reverse = False)
    rows = len(C)
    cols = A + 1
    T = [[0 for j in range(cols)] for i in range(rows)]
    for i in range(rows):        
        for j in range(1, cols):
            if j < C[i]:
                T[i][j] = T[i - 1][j] if i > 0 else INF
            else:
                T[i][j] = min(T[i - 1][j] if i > 0 else INF, 1 + T[i][j - C[i]])
    return T[rows - 1][cols - 1]

#*** 1 is required in C

A = 10
C = [1, 5]
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 10
C = [1, 5, 10]
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 4
C = [1, 2, 3]
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 5
C = [1, 2]
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 250
C = list(range(1, 51))
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 250
C = [1, 5, 10, 25, 50]
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 50
C = list(range(1, 51))
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 9
C = [1, 2, 3, 5]
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 30
C = [1, 15, 25]
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

A = 10
C = [1, 2, 5, 3, 6]
print ("Greedy: %d\n    DP: %d" % (greedyCoinsChange(A, C), dpCoinsChange(A, C)))

import timeit

greedyTime = """
def greedyCoinsChange(A, C):
    C.sort(reverse = True)
    counter = 0
    for c in C:
        if (A > 0):
            counter = counter + (A // c)
            A = A % c
        else:
            break
    return counter
A = 12345
C = list(range(1, 500))
#A = 1000
#C = list(range(1, 10000))
greedyCoinsChange(A, C)
"""

dpTime = """
import sys
INF = sys.maxsize

def dpCoinsChange(A, C):
    C.sort(reverse = False)
    rows = len(C)
    cols = A + 1
    T = [[0 for j in range(cols)] for i in range(rows)]
    for i in range(rows):        
        for j in range(1, cols):
            if j < C[i]:
                T[i][j] = T[i - 1][j] if i > 0 else INF
            else:
                T[i][j] = min(T[i - 1][j] if i > 0 else INF, 1 + T[i][j - C[i]])
    return T[rows - 1][cols - 1]
A = 12345
C = list(range(1, 500))
#A = 1000
#C = list(range(1, 10000))
dpCoinsChange(A, C)
"""

print ("Greedy: %f s\n    DP: %f s" % (timeit.timeit(greedyTime, number = 1), timeit.timeit(dpTime, number = 1)))