concept · INFO-CS-ADS-176Coin 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
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.
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.
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