✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-176

Coin Change Problem

Understand how dynamic programming determines the minimum number of coins needed to make a target amount or counts the possible combinations of coins.

Explanation

Overview

The Coin Change Problem is a family of problems involving a set of coin denominations and a target amount. Common versions ask for the minimum number of coins required to form the amount or the number of distinct combinations that produce it.

Key concepts

Minimum-cost optimization; Unbounded item selection; Base case; Unreachable states; Dynamic programming recurrence

Variables

a: The target amount currently being calculated.; coin: A permitted coin denomination.; dp[a]: The minimum number of coins needed to make amount a.; INF: A value representing an amount that cannot currently be formed.

Complexity

minimumCoins: O(A × C) time and O(A) space.; variables: A is the target amount and C is the number of coin denominations.

Example

coins: 1; 3; amount: 6; selectedCoins: 3; 3; minimumCoins: 2; explanation: Two coins of denomination 3 form the target amount. Other combinations, such as 4 + 1 + 1, use more coins.

Pseudocode

function minCoins(coins, amount):
dp = array of size amount + 1 filled with INF
dp[0] = 0
for a = 1 to amount:
for coin in coins:
if coin <= a and dp[a - coin] != INF:
dp[a] = min(dp[a], 1 + dp[a - coin])
if dp[amount] == INF:
return -1
return dp[amount]

Applications

Currency and denomination systems.; Change-making machines.; Resource decomposition.; Minimum-cost combination problems.; Counting combinations.

Variables

A

The target amount currently being calculated.

Coin

A permitted coin denomination.

Dp[a]

The minimum number of coins needed to make amount a.

INF

A value representing an amount that cannot currently be formed.

Example or application

Coins

  • 1

  • 3

  • 4

Amount

6

Selected Coins

  • 3

  • 3

Minimum Coins

2

Explanation

Two coins of denomination 3 form the target amount. Other combinations, such as 4 + 1 + 1, use more coins.

Definition

The Coin Change Problem is a family of problems involving a set of coin denominations and a target amount. Common versions ask for the minimum number of coins required to form the amount or the number of distinct combinations that produce it.

Mathematical Representation

For the minimum-coin version: dp[a] = min(dp[a], 1 + dp[a - coin]) for each coin <= a, with dp[0] = 0.

Approaches

Minimum Coins

Builds the minimum number of coins for every amount from zero to the target.

Memoization

Uses recursion and stores the minimum result for each amount.

Tabulation

Calculates smaller amounts before larger amounts.

Combination Counting

Uses a separate recurrence to count combinations, often iterating over coin denominations first to avoid counting different orders as separate combinations.

Pseudocode

function minCoins(coins, amount):
dp = array of size amount + 1 filled with INF
dp[0] = 0
for a = 1 to amount:
for coin in coins:
if coin <= a and dp[a - coin] != INF:
dp[a] = min(dp[a], 1 + dp[a - coin])
if dp[amount] == INF:
return -1
return dp[amount]

Complexity

Minimum Coins

O(A × C) time and O(A) space.

Variables

A is the target amount and C is the number of coin denominations.

Key Concepts

  • Minimum-cost optimization

  • Unbounded item selection

  • Base case

  • Unreachable states

  • Dynamic programming recurrence

Advantages

  • Finds an optimal minimum-coin solution for arbitrary supported denominations.

  • Handles cases where a greedy choice is not optimal.

  • Can determine whether an amount is reachable.

  • Can be adapted to count combinations or ordered sequences.

Limitations

  • The common O(A × C) solution is pseudo-polynomial in the numeric target amount.

  • Large target amounts may require substantial memory.

  • Different versions of the problem use different recurrence relations and iteration orders.

Applications

  • Currency and denomination systems.

  • Change-making machines.

  • Resource decomposition.

  • Minimum-cost combination problems.

  • Counting combinations.

Related Topics

  • Unbounded Knapsack Problem

  • 0/1 Knapsack Problem

  • Rod Cutting Problem

  • Dynamic Programming

Practice Question

Using coins [1, 3, 4], what is the minimum number of coins needed to make amount 6?

Practice Answer

2 coins: 3 + 3.

Learning Objectives

  • Explain the central idea and purpose of coin change problem.

  • Identify the assumptions, inputs, and conditions relevant to coin change problem.

  • Evaluate an application of coin change problem for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Dynamic Programming Applications

Suggest a correction or source · More in Algorithms & Data Structures