Python Dynamic Coin Change Algorithm

dynamicCoinChange.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

# T: an array containing the values of the coins
# L: integer wich is the total to give back
# Output: Minimal number of coins needed to make a total of L
def dynamicCoinChange( T, L ):

	Opt = [0 for i in range(0, L+1)]
	
	n = len(T)
	for i in range(1, L+1):
		smallest = float("inf")
		for j in range(0, n):
			if (T[j] <= i):
				smallest = min(smallest, Opt[i - T[j]]) 
		Opt[i] = 1 + smallest 
	return Opt[L]


# Coin change situations
problems = [
	# [[1, 5, 10, 20, 50, 100, 200],  10000000],
	[[1, 3, 4],  20],
	[[1, 2, 3],  9],
	[[1, 2, 3],  10],
	[[1, 5], 13923],
	[[7, 22, 71, 231], 753],
	[[3, 5, 12], 25],
	[[800], 800],
	[[2], 50000]
]

# Test Loop
for T, L in problems:
	S = dynamicCoinChange(T, L)
	print "dynamicCoinChange(T, L)"
	print "T =", T
	print "L =", L
	print "Answer =", S

output

dynamicCoinChange(T, L)
T = [1, 3, 4]
L = 20
Answer = 5
dynamicCoinChange(T, L)
T = [1, 2, 3]
L = 9
Answer = 3
dynamicCoinChange(T, L)
T = [1, 2, 3]
L = 10
Answer = 4
dynamicCoinChange(T, L)
T = [1, 5]
L = 13923
Answer = 2787
dynamicCoinChange(T, L)
T = [7, 22, 71, 231]
L = 753
Answer = 7
dynamicCoinChange(T, L)
T = [3, 5, 12]
L = 25
Answer = 4
dynamicCoinChange(T, L)
T = [800]
L = 800
Answer = 1
dynamicCoinChange(T, L)
T = [2]
L = 50000
Answer = 25000
[Finished in 0.2s]