Coin Change Problem
In this page:
Problem Idea
The classic version of coin change asks for the minimum number of coins from a given set of denominations that add up to exactly a target amount, or reports that it's impossible if no combination works.
Example: Problem Idea
#include <iostream>
using namespace std;
int main() {
int coins[] = {1, 3, 4}, amount = 6;
cout << "Fewest coins from {1,3,4} to make " << amount << ", or -1 if impossible";
return 0;
}public class Main {
public static void main(String[] args) {
int[] coins = {1, 3, 4};
int amount = 6;
System.out.println("Fewest coins from {1,3,4} to make " + amount + ", or -1 if impossible");
}
}coins, amount = [1, 3, 4], 6
print(f"Fewest coins from {{1,3,4}} to make {amount}, or -1 if impossible")#include <stdio.h>
int main() {
int coins[] = {1, 3, 4}, amount = 6;
printf("Fewest coins from {1,3,4} to make %d, or -1 if impossible", amount);
return 0;
}Login to try C/C++/Java code in the editor
DP State
dp[x] stores the fewest coins needed to make amount x, built up from dp[0] = 0 (zero coins for zero amount) so that every larger amount can be computed from smaller ones already solved.
Example: DP State
#include <iostream>
using namespace std;
int main() {
int dp[7]; dp[0] = 0;
cout << "dp[0] = 0 coins for amount 0; every dp[x] for x>0 built from smaller amounts already solved";
return 0;
}public class Main {
public static void main(String[] args) {
int[] dp = new int[7]; dp[0] = 0;
System.out.println("dp[0] = 0 coins for amount 0; every dp[x] for x>0 built from smaller amounts already solved");
}
}dp = [0] * 7
print("dp[0] = 0 coins for amount 0; every dp[x] for x>0 built from smaller amounts already solved")#include <stdio.h>
int main() {
int dp[7] = {0};
printf("dp[0] = 0 coins for amount 0; every dp[x] for x>0 built from smaller amounts already solved");
return 0;
}Login to try C/C++/Java code in the editor
Transition
For each coin denomination that's small enough to fit into amount x, one option is using that coin plus however many coins were needed for the remaining amount (x minus the coin's value) — dp[x] takes the minimum across every coin that fits.
Example: Transition
#include <iostream>
using namespace std;
int main() {
int coins[] = {1,3,4}, amount = 6;
int dp[7]; dp[0] = 0;
for (int x = 1; x <= amount; x++) {
dp[x] = 1000000;
for (int c : coins) if (c <= x) dp[x] = min(dp[x], dp[x-c] + 1);
}
cout << "Fewest coins for " << amount << ": " << dp[amount];
return 0;
}public class Main {
public static void main(String[] args) {
int[] coins = {1,3,4};
int amount = 6;
int[] dp = new int[7]; dp[0] = 0;
for (int x = 1; x <= amount; x++) {
dp[x] = 1000000;
for (int c : coins) if (c <= x) dp[x] = Math.min(dp[x], dp[x-c] + 1);
}
System.out.println("Fewest coins for " + amount + ": " + dp[amount]);
}
}coins, amount = [1,3,4], 6
dp = [0] + [float('inf')] * amount
for x in range(1, amount+1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x-c] + 1)
print("Fewest coins for", amount, ":", dp[amount])#include <stdio.h>
int main() {
int coins[] = {1,3,4}, amount = 6;
int dp[7]; dp[0] = 0;
for (int x = 1; x <= amount; x++) {
dp[x] = 1000000;
for (int i = 0; i < 3; i++) if (coins[i] <= x && dp[x-coins[i]]+1 < dp[x]) dp[x] = dp[x-coins[i]]+1;
}
printf("Fewest coins for %d: %d", amount, dp[amount]);
return 0;
}Login to try C/C++/Java code in the editor
Ways to Make Change
A closely related but different question asks how many distinct combinations of coins can make the target amount, rather than the fewest coins — that variant uses the same table shape but counts (sums) possibilities instead of minimizing.
Example: Ways to Make Change
#include <iostream>
using namespace std;
int main() {
int coins[] = {1,2,5}, amount = 5;
int dp[6] = {0}; dp[0] = 1;
for (int c : coins)
for (int x = c; x <= amount; x++) dp[x] += dp[x-c];
cout << "Distinct combinations to make " << amount << ": " << dp[amount];
return 0;
}public class Main {
public static void main(String[] args) {
int[] coins = {1,2,5};
int amount = 5;
int[] dp = new int[6]; dp[0] = 1;
for (int c : coins)
for (int x = c; x <= amount; x++) dp[x] += dp[x-c];
System.out.println("Distinct combinations to make " + amount + ": " + dp[amount]);
}
}coins, amount = [1,2,5], 5
dp = [0]*(amount+1)
dp[0] = 1
for c in coins:
for x in range(c, amount+1):
dp[x] += dp[x-c]
print("Distinct combinations to make", amount, ":", dp[amount])#include <stdio.h>
int main() {
int coins[] = {1,2,5}, amount = 5;
int dp[6] = {0}; dp[0] = 1;
for (int i = 0; i < 3; i++)
for (int x = coins[i]; x <= amount; x++) dp[x] += dp[x-coins[i]];
printf("Distinct combinations to make %d: %d", amount, dp[amount]);
return 0;
}Login to try C/C++/Java code in the editor
Practice
Because any denomination can be reused as many times as needed, coin change is a direct real-world example of the unbounded knapsack pattern applied to making change at a cash register.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Coin change is unbounded knapsack applied directly to making change at a cash register";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Coin change is unbounded knapsack applied directly to making change at a cash register");
}
}print("Coin change is unbounded knapsack applied directly to making change at a cash register")#include <stdio.h>
int main() {
printf("Coin change is unbounded knapsack applied directly to making change at a cash register");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: