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]

What is the time complexity of this solution?

@Lobsterrr O(kn) when k is the number of coin and n is the total change amount.

this sucks

This is the most efficient , shortest and readable solution to this problem.
I did a little modification to get the coins array as well as it was part of my exercise.

def dynamicCoinChange( T, L ):

      Opt = [0 for i in range(0, L+1)]
      sets = {i:[] for i in range(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]]) 
                       if smallest == Opt[i - T[j]]:
                             sets[i] = [T[j]] + sets[i-T[j]]
            Opt[i] = 1 + smallest 
      return Opt[L],sorted(sets[L])

can you tell me how to get a list as an output which will give me the number of coins used for each demonination. Like for test 1 would be [0 ,0, 5]