Practice › Dynamic Programming
Coin Change (Minimum Coins)
Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Goldman Sachs, Paytm
Using coins of the given denominations (unlimited supply), make the amount with the fewest coins. Print that number, or -1 if it is impossible.
Input
First line: n. Second line: n denominations. Third line: amount.
Output
The minimum number of coins, or -1.
Constraints
- 1 ≤ n ≤ 12
- 1 ≤ coin ≤ 10^4
- 0 ≤ amount ≤ 10^4
Greedy fails for some coin systems — use dp[x] = 1 + min(dp[x − coin]).
Example 1
Input
3 1 2 5 11
Output
3
Example 2
Input
1 2 3
Output
-1
Hints
- Greedy (always take the biggest coin) fails: coins {1, 3, 4}, amount 6 → greedy uses 4+1+1, best is 3+3.
- dp[x] = fewest coins for amount x = 1 + min(dp[x − c]) over coins c ≤ x, with dp[0] = 0.
Approach
Fill dp[0..amount] from small to large, using "infinity" for unreachable amounts. For each x and each coin c ≤ x, if dp[x − c] is reachable, try dp[x − c] + 1. The answer is dp[amount], or -1 if it's still infinity. Amount 0 needs 0 coins.
Complexity: O(amount · n) time · O(amount) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, amount;
cin >> n;
vector<int> coins(n);
for (auto &c : coins) cin >> c;
cin >> amount;
const int INF = INT_MAX;
vector<int> dp(amount + 1, INF);
dp[0] = 0;
for (int x = 1; x <= amount; x++)
for (int c : coins)
if (c <= x && dp[x - c] != INF) dp[x] = min(dp[x], dp[x - c] + 1);
cout << (dp[amount] == INF ? -1 : dp[amount]) << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
coins, amount = data[1 : n + 1], data[n + 1]
INF = float("inf")
dp = [0] + [INF] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x and dp[x - c] + 1 < dp[x]:
dp[x] = dp[x - c] + 1
print(-1 if dp[amount] == INF else dp[amount])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] coins = new int[n];
for (int i = 0; i < n; i++) coins[i] = sc.nextInt();
int amount = sc.nextInt();
final int INF = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int x = 1; x <= amount; x++)
for (int c : coins)
if (c <= x && dp[x - c] != INF) dp[x] = Math.min(dp[x], dp[x - c] + 1);
System.out.println(dp[amount] == INF ? -1 : dp[amount]);
}
}Solve Coin Change (Minimum Coins) online · All practice problems