#Find minimum number of coins that make a given value
#Given a value V, if we want to make change for V cents, and we have infinite supply
#of each of C = { C1, C2, .. , Cm} valued coins, what is the minimum number of coins to make the change?
def createMatrix(n, s):
    m = [[ 0 for col in range(n+1)] for row in range(len(s)+1)]
    return m

def foo(n, s):
    matrix = createMatrix(n,s)
    for row in range(len(s)):
        for col in range(n+1):
            if(s[row] == col):
                matrix[row+1][col] = 1
            elif(s[row] > col):
                #Copy the value from top
                matrix[row+1][col] = matrix[row][col]
            else:
                #Get the value from those many steps behind
                value = matrix[row+1][col - s[row]]
                #If this value is 0 then get the value form top
                if value == 0:
                    matrix[row+1][col] = matrix[row][col]
                if(value > 0):
                    #Find top value
                    top = matrix[row][col]
                    if top == 0:
                        matrix[row+1][col] = value+1
                    else:
                        matrix[row+1][col] = min(top, value+1)
    print matrix
    print "we need a minimum of "+str(matrix[len(s)][n])

#Main Program
foo(10, [2,5,3,6])
foo(30, [25, 10, 5])
foo(11, [9, 6, 5, 1])