Python – Coin Change Problem

Python – Coin Change Problem

The Coin Change Problem is a classic dynamic programming challenge. Given a list of coin denominations and a target amount, the goal is to determine the fewest number of coins required to make that amount. If the amount cannot be formed with the available coins, the solution should indicate so by returning -1.

Problem Statement

Given an array coins representing the coin denominations and an integer amount, find the minimum number of coins needed to make up the given amount. If it is not possible to form the amount using the coins provided, return -1.

For instance, if coins = [1, 2, 5] and amount = 11, the minimum number of coins required is 3 (5 + 5 + 1).

Sample Input and Output

Example 1:

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

# Output:
3

# Explanation:
# The minimum number of coins required to form 11 is 3 (5 + 5 + 1).

Example 2:

# Input:
coins = [2]
amount = 3

# Output:
-1

# Explanation:
# It is not possible to form the amount 3 with coins of denomination 2, so the output is -1.

Solution Approach

We solve the problem using dynamic programming by defining an array dp where dp[i] represents the minimum number of coins required to make up the amount i. The approach consists of the following steps:

1. Initialize a dp array of length amount + 1 with a value greater than the maximum possible (we use amount + 1 as a substitute for infinity). Set dp[0] = 0 because no coins are needed to make an amount of 0.
2. For each amount i from 1 to amount, iterate through each coin in coins. If the coin value is less than or equal to i, update dp[i] as the minimum of its current value and dp[i - coin] + 1.
3. After processing all sub-amounts, if dp[amount] is still greater than amount, it indicates that the amount cannot be formed; hence, return -1. Otherwise, return dp[amount].

Python Program

def coin_change(coins, amount):
    """
    Compute the minimum number of coins required to make up the given amount.
    
    Parameters:
    coins (List[int]): The list of coin denominations.
    amount (int): The target amount.
    
    Returns:
    int: The minimum number of coins needed, or -1 if the amount cannot be formed.
    """
    # Initialize dp array with a value (amount+1) that represents infinity.
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins are needed to make amount 0

    # Fill the dp array
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    # If no solution was found, dp[amount] will be greater than amount
    return dp[amount] if dp[amount] <= amount else -1

# Test examples:
print("Example 1:")
coins1 = [1, 2, 5]
amount1 = 11
print("Input: coins =", coins1, ", amount =", amount1)
print("Output:", coin_change(coins1, amount1))  # Expected output: 3

print("\nExample 2:")
coins2 = [2]
amount2 = 3
print("Input: coins =", coins2, ", amount =", amount2)
print("Output:", coin_change(coins2, amount2))  # Expected output: -1

Explanation: The function coin_change initializes a DP array where each index represents an amount. It then iteratively computes the minimum number of coins required for each amount by considering every coin denomination. The final value, dp[amount], holds the answer. If this value remains above the feasible limit, it means the amount cannot be constructed with the given coins, and the function returns -1.

Conclusion

The Coin Change Problem is a fundamental dynamic programming challenge that demonstrates how breaking a problem into subproblems can lead to an efficient solution. By using a DP array to track the minimum coins needed for each sub-amount, we can effectively solve the problem for any given set of coin denominations and target amount. This approach is highly applicable in algorithm interviews and practical programming challenges.