Coin Change Problem#

Welcome to Day 37 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Coin Change Problem, a classic dynamic programming problem with applications in various fields, including currency systems and algorithmic trading.

What is the Coin Change Problem?#

The Coin Change Problem is about finding the number of ways to make change for a particular amount of money, given a set of coin denominations. There are two common variations of this problem:

1. Finding the total number of ways to make the change.
2. Finding the minimum number of coins needed to make the change.

We’ll explore both variations in this lesson.

Variation 1: Number of Ways to Make Change#

Problem Statement#

Given an amount N and a set of coin denominations, find the total number of ways to make change for N.

Naive Recursive Approach#

Let’s start with a naive recursive implementation:

 1def coin_change_recursive(coins, amount):
 2    def recursive_helper(index, remaining):
 3        if remaining == 0:
 4            return 1
 5        if remaining < 0 or index >= len(coins):
 6            return 0
 7        
 8        # Include the current coin or exclude it
 9        return (recursive_helper(index, remaining - coins[index]) + 
10                recursive_helper(index + 1, remaining))
11    
12    return recursive_helper(0, amount)
13
14# Example usage
15coins = [1, 2, 5]
16amount = 5
17print(f"Number of ways to make change for {amount}: {coin_change_recursive(coins, amount)}")

This approach has a time complexity of O(2^n), where n is the amount, making it inefficient for larger amounts.

Dynamic Programming Approach#

We can significantly improve the efficiency using Dynamic Programming.

 1def coin_change_dp(coins, amount):
 2    dp = [0] * (amount + 1)
 3    dp[0] = 1  # Base case: there's one way to make change for 0
 4    
 5    for coin in coins:
 6        for i in range(coin, amount + 1):
 7            dp[i] += dp[i - coin]
 8    
 9    return dp[amount]
10
11# Example usage
12coins = [1, 2, 5]
13amount = 5
14print(f"Number of ways to make change for {amount}: {coin_change_dp(coins, amount)}")

This approach has a time complexity of O(amount * len(coins)) and a space complexity of O(amount).

Variation 2: Minimum Number of Coins#

Problem Statement#

Given an amount N and a set of coin denominations, find the minimum number of coins needed to make change for N.

Dynamic Programming Approach#

 1def min_coins_dp(coins, amount):
 2    dp = [float('inf')] * (amount + 1)
 3    dp[0] = 0
 4    
 5    for i in range(1, amount + 1):
 6        for coin in coins:
 7            if coin <= i:
 8                dp[i] = min(dp[i], dp[i - coin] + 1)
 9    
10    return dp[amount] if dp[amount] != float('inf') else -1
11
12# Example usage
13coins = [1, 2, 5]
14amount = 11
15print(f"Minimum coins needed for {amount}: {min_coins_dp(coins, amount)}")

This approach also has a time complexity of O(amount * len(coins)) and a space complexity of O(amount).

Printing the Coin Combination#

We can modify our solution to also print the actual combination of coins used:

 1def min_coins_with_combination(coins, amount):
 2    dp = [float('inf')] * (amount + 1)
 3    dp[0] = 0
 4    coin_used = [-1] * (amount + 1)
 5    
 6    for i in range(1, amount + 1):
 7        for coin in coins:
 8            if coin <= i and dp[i - coin] + 1 < dp[i]:
 9                dp[i] = dp[i - coin] + 1
10                coin_used[i] = coin
11    
12    if dp[amount] == float('inf'):
13        return -1, []
14    
15    # Reconstruct the coin combination
16    combination = []
17    current = amount
18    while current > 0:
19        combination.append(coin_used[current])
20        current -= coin_used[current]
21    
22    return dp[amount], combination
23
24# Example usage
25coins = [1, 2, 5]
26amount = 11
27min_coins, combination = min_coins_with_combination(coins, amount)
28print(f"Minimum coins needed for {amount}: {min_coins}")
29print(f"Coin combination: {combination}")

Applications of the Coin Change Problem#

1. Currency systems and cash dispensing machines
2. Financial algorithms for minimizing transaction costs
3. Resource allocation in computer systems
4. Solving scheduling problems with discrete time units

Exercise#

1. Modify the first variation to find the number of unique ways to make change (where the order of coins doesn’t matter).

2. Implement a solution for the case where you have a limited supply of each coin denomination.

3. Solve the Coin Change Problem for a system where some coin denominations might not be available (i.e., you’re given a set of possible denominations, but not all are guaranteed to be in your coin set).

Summary#

Today, we explored the Coin Change Problem, a classic example of dynamic programming. We implemented solutions for two variations of the problem: finding the number of ways to make change and finding the minimum number of coins needed.

Understanding the Coin Change Problem and its solutions provides valuable insights into dynamic programming techniques and their applications in optimization and counting problems.

Tomorrow, we’ll dive into another fundamental algorithm: the Floyd-Warshall algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. Stay tuned!

Solution#

 1def coin_change_limited(coins, counts, amount):
 2    # dp[a] = number of ways to make amount a using coins considered so far
 3    dp = [0] * (amount + 1)
 4    dp[0] = 1
 5    for coin, limit in zip(coins, counts):
 6        # iterate amount downward so each coin type is layered once
 7        new_dp = dp[:]
 8        for a in range(1, amount + 1):
 9            total = 0
10            for k in range(1, limit + 1):
11                if k * coin > a:
12                    break
13                total += dp[a - k * coin]
14            new_dp[a] += total
15        dp = new_dp
16    return dp[amount]
17
18# Example usage
19coins = [1, 2, 5]
20counts = [3, 2, 1]  # three 1s, two 2s, one 5
21# Valid combos: {5}, {1,2,2}, {1,1,1,2}  (five 1s is not possible: only three)
22print(f"Number of ways: {coin_change_limited(coins, counts, 5)}")  # 3