Making Change Problem Using Dynamic Programming: A Complete Guide

by

Finding the fewest coins required to generate a specific amount of change given a variety of coin denominations is the aim of the Making Change Problem, a well-known dynamic programming problem.

It is an optimization problem that dynamic programming approaches may effectively handle.

Problem Description

The aim is to determine the smallest number of coins that sum up to the desired amount given a set of denominations (coins). If the specified denominations cannot be used to produce the precise change, the solution should return an appropriate answer, such “infinity” or “impossible.”

Approach: Dynamic Programming Solution

Steps:

  1. Initialize a DP table: Create a table (or an array) dp[] where dp[i] will store the minimum number of coins needed to make the amount i.
  2. Base Case: Set dp[0] = 0 because no coins are needed to make the amount 0.
  3. Fill the DP Table: For each coin in the given set of coins, iterate through all amounts from the coin value up to the target amount. For each amount, update the dp[] table to reflect the minimum number of coins needed to make that amount.
  4. Return the Result: After filling the DP table, the value at dp[target] will represent the minimum number of coins required to make the target amount.

Example

Let’s go through an example to clarify this approach.

  • Denominations: [1, 2, 5] (coins available)
  • Target Amount: 11

Step-by-Step Dynamic Programming Solution:

  1. Initialize the DP Table:
   dp = [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]

Set dp[0] = 0 because no coins are needed to make amount 0:

   dp = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
  1. Iterate Over Each Coin:
    For each coin, iterate through the amounts from the coin’s value to the target amount and update the DP table.
  • For coin 1: 
dp[1] = min(dp[1], dp[0] + 1) => dp[1] = 1
dp[2] = min(dp[2], dp[1] + 1) => dp[2] = 2
dp[3] = min(dp[3], dp[2] + 1) => dp[3] = 3
dp[4] = min(dp[4], dp[3] + 1) => dp[4] = 4
dp[5] = min(dp[5], dp[4] + 1) => dp[5] = 5
dp[6] = min(dp[6], dp[5] + 1) => dp[6] = 6
dp[7] = min(dp[7], dp[6] + 1) => dp[7] = 7
dp[8] = min(dp[8], dp[7] + 1) => dp[8] = 8
dp[9] = min(dp[9], dp[8] + 1) => dp[9] = 9
dp[10] = min(dp[10], dp[9] + 1) => dp[10] = 10
dp[11] = min(dp[11], dp[10] + 1) => dp[11] = 11

After processing coin 1, the DP table looks like:

   dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
  • For coin 2: 
dp[2] = min(dp[2], dp[0] + 1) => dp[2] = 1
dp[3] = min(dp[3], dp[1] + 1) => dp[3] = 2
dp[4] = min(dp[4], dp[2] + 1) => dp[4] = 2
dp[5] = min(dp[5], dp[3] + 1) => dp[5] = 3
dp[6] = min(dp[6], dp[4] + 1) => dp[6] = 3
dp[7] = min(dp[7], dp[5] + 1) => dp[7] = 4
dp[8] = min(dp[8], dp[6] + 1) => dp[8] = 4
dp[9] = min(dp[9], dp[7] + 1) => dp[9] = 5
dp[10] = min(dp[10], dp[8] + 1) => dp[10] = 5
dp[11] = min(dp[11], dp[9] + 1) => dp[11] = 6

After processing coin 2, the DP table looks like:

   dp = [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
  • For coin 5: 
dp[5] = min(dp[5], dp[0] + 1) => dp[5] = 1
dp[6] = min(dp[6], dp[1] + 1) => dp[6] = 2
dp[7] = min(dp[7], dp[2] + 1) => dp[7] = 3
dp[8] = min(dp[8], dp[3] + 1) => dp[8] = 4
dp[9] = min(dp[9], dp[4] + 1) => dp[9] = 3
dp[10] = min(dp[10], dp[5] + 1) => dp[10] = 2
dp[11] = min(dp[11], dp[6] + 1) => dp[11] = 3

After processing coin 5, the DP table looks like:

   dp = [0, 1, 1, 2, 2, 1, 2, 3, 4, 3, 2, 3]
  1. The Final Result:
    The minimum number of coins required to make the amount 11 is dp[11] = 3.

Thus, the optimal solution is to use:

  • 1 coin of 5
  • 3 coins of 2

General Dynamic Programming Code

def minCoins(coins, target):
    # Create a DP array initialized to infinity
    dp = [float('inf')] * (target + 1)

    # Base case: 0 coins are needed to make 0 amount
    dp[0] = 0

    # Loop over each coin
    for coin in coins:
        for i in range(coin, target + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    # If dp[target] is still infinity, it means it's not possible to make change
    if dp[target] == float('inf'):
        return -1  # Not possible to make change
    return dp[target]

# Example Usage
coins = [1, 2, 5]
target = 11
print(minCoins(coins, target))  # Output: 3

Time Complexity:

  • Time Complexity: O(n * m), where {mis the number of currency denominations andn` is the goal amount.
  • Space Complexity: O(n), where n is the target amount.

This solution is optimal for solving the Making Change Problem using dynamic programming.

Leave a Comment