Change Problem (Dynamic Programming, Recursive and Greedy)

change.py

def find_max_coin(money, coins):
    max_coin = float('-inf')
    for coin in coins:
        if money - coin >= 0 and coin > max_coin:
            max_coin = coin
    return max_coin

def change_greedy(money, coins):
    """
    Running time: 
    O(mn) where n is the number of coins and m is range of 0 to money
    """
    change = []
    while money > 0:
        coin = find_max_coin(money, coins)
        change.append(coin)
        money = money - coin
    return change

def change_greedy_sorted(money, coins):
    """
    Running time: 
    O(max(n, m))
    """
    change = []
    sorted_coins = sorted(coins, reverse=True)
    for coin in coins:
        while money - coin >= 0: 
            money -= coin
            change.append(coin)
    return coin

def change_recursive(money, coins):
    """
    Find minimum number of coins to give change for money
    Args:
    (array) coins denominations
    (float) money for which change is needed
    
    Returns:
    Minimum number of coins
    
    Running time: 
    O(m*n^2)
    """
    if money == 0:
        return 0
    min_num_coins = float('inf')
    for i in range(len(coins)):
        if money >= coins[i]:
            num_coins = change_recursive(money - coins[i], coins)
            if num_coins + 1 <= min_num_coins:
                min_num_coins = num_coins + 1
    return min_num_coins
    
def change_dp(money, coins):
    """
    Dynamic Programming
    Running time:
    O(mn)
    """
    min_num_coins = [0] * (money + 1)
    for m in range(1, money + 1):
        min_num_coins[m] = float('inf')
        for coin in coins:
            if m >= coin:
                num_coins = min_num_coins[m - coin] + 1
                if num_coins < min_num_coins[m]:
                    min_num_coins[m] = num_coins
    return min_num_coins, min_num_coins[money]

assert(change_dp(9, [6, 5, 1]) == ([0, 1, 2, 3, 4, 1, 1, 2, 3, 4], 4))