coin_change.py

'''
Coin Change

You are given coins of different denominations and a total amount of money amount.
Write a function to compute the fewest number of coins that you need to make up that amount.
If that amount of money cannot be made up by any combination of the coins, return -1.

Input: coins = [1, 2, 5], amount = 11
Output: 3

Input: coins = [2], amount = 3
Output: -1

=========================================
Dynamic programming solution 1
    Time Complexity:    O(A*C)  , A = amount, C = coins
    Space Complexity:   O(A)
Dynamic programming solution 2 (don't need the whole array, just use modulo to iterate through the partial array)
    Time Complexity:    O(A*C)  , A = amount, C = coins
    Space Complexity:   O(maxCoin)
'''


##############
# Solution 1 #
##############

def coin_change_1(coins, amount):
    if amount == 0:
        return 0
    if len(coins) == 0:
        return -1

    max_value = amount + 1  # use this instead of math.inf
    dp = [max_value for i in range(max_value)]
    dp[0] = 0

    for i in range(1, max_value):
        for c in coins:
            if c <= i:
                # search on previous positions for min coins needed
                dp[i] = min(dp[i], dp[i - c] + 1)

    if (dp[amount] == max_value):
        return -1
    return dp[amount]


##############
# Solution 2 #
##############

def coin_change_2(coins, amount):
    if amount == 0:
        return 0
    if len(coins) == 0:
        return -1

    max_value = amount + 1
    max_coin = min(max_value, max(coins) + 1)
    dp = [max_value for i in range(max_coin)]
    dp[0] = 0

    for i in range(1, max_value):
        i_mod = i % max_coin
        dp[i_mod] = max_value # reset current position

        for c in coins:
            if c <= i:
                # search on previous positions for min coins needed
                dp[i_mod] = min(dp[i_mod], dp[(i - c) % max_coin] + 1)

    if (dp[amount % max_coin] == max_value):
        return -1
    return dp[amount % max_coin]


###########
# Testing #
###########

# Test 1
# Correct result => 3
coins = [1, 2, 5]
amount = 11
print(coin_change_1(coins, amount))
print(coin_change_2(coins, amount))

# Test 2
# Correct result => -1
coins = [2]
amount = 3
print(coin_change_1(coins, amount))
print(coin_change_2(coins, amount))