coin_sum.py

def calculate_coins(c, s):
    #sort the coins
    c = sorted(c)
    
    # remove the coins with values bigger than s
    c = [ci for ci in filter(lambda cv: cv<=s, c)]
    
    # sentinel value to represent that one coin sum is not possible. We can use s + 1 as sentinel value to represent
    # that case. Mininum value of a coin is 1 so more than s coins can not make a sum of s
    sentinel = s+1
    
    #output values list ( lenght of array s+1). After the execeution of the for loop later, an element o[i] of this list
    # will contain the minimum number of ways to create the sum i
    o = [sentinel for i in range(0, s+1)]
    
    # number of ways of creating sum 0 is 0
    o[0] = 0
    
    for i in range(0, s+1):
        for ci in c:
            ni = i + ci
            # maximum index in the list is s and we do not want to go past that
            if ni > s:
                continue
            # Dynamic programming logic of using the subproblem solution to calculate the problem but in bottom up manner
            o[ni] = o[ni] if o[i] + 1 > o[ni] else o[i] + 1
    
    return -1 if o[s] == sentinel else o[s]


assert calculate_coins([1, 2], 0) is 0
assert calculate_coins([2, 2], 0) is 0
assert calculate_coins([2, 5, 10, 11], 10) is 1
assert calculate_coins([2, 5], 10) is 2
assert calculate_coins([10, 20], 9) is -1
assert calculate_coins([9, 20], 9) is 1
assert calculate_coins([5, 3], 7) is -1
assert calculate_coins([5, 2, 3], 8) is 2