Coin Change Problem

December 23, 2023

Problem #

Given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount.

Solution #

Here’s the Python code for finding the minimum number of coins needed to make a target amount, given a set of coin denominations:

def min_coins(coins, amount):
    # Create a table to store the minimum number of coins for each amount
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins are needed to make amount 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# Example usage
coins = [1, 2, 5]
amount = 11
min_number_of_coins = min_coins(coins, amount)

In this code:

• A dynamic programming approach is used where an array dp of size amount + 1 is initialized with float('inf'), representing the minimum number of coins needed for each amount up to the target amount.
• dp[0] is set to 0 because no coins are needed to make an amount of 0.
• The function iterates over each sub-amount from 1 to amount, and for each sub-amount, it checks every coin denomination to find the minimum number of coins needed.
• If the current sub-amount is greater than or equal to a coin denomination, it updates dp[i] with the minimum value between its current value and 1 + dp[i - coin].
• After filling the table, dp[amount] holds the minimum number of coins needed for the target amount. If dp[amount] is still float('inf'), it means it’s not possible to make that amount with the given coins, so the function returns -1.

For the example with coins = [1, 2, 5] and amount = 11, the function returns 3, indicating that the minimum number of coins required to make 11 is 3 (for example, using two 5 coins and one 1 coin).