# Title: Coin change
# Heading: Python Program for the Coin Change Problem (Minimum Coins)
# Level: intermediate
# Tags: coin change, minimum coins, dynamic programming, dp, bottom-up
# Time: O(n × k)
# Space: O(n)
# About: Finds the fewest coins that add up to an amount by solving every smaller amount first, or -1 when no mix of the coins makes it.

def min_coins(coins, amount):
    """The fewest coins that add up to amount, or -1 if none do."""
    # fewest[a]: the fewest coins for amount a (inf: no way yet)
    fewest = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                fewest[a] = min(fewest[a], fewest[a - coin] + 1)
    if fewest[amount] == float("inf"):
        return -1  # no mix of the coins makes this amount
    return fewest[amount]


coins = [2, 5]
print("Fewest coins for 6:", min_coins(coins, 6))
print("Fewest coins for 3:", min_coins(coins, 3))