Practice › Dynamic Programming
Coin Change (Number of Ways)
Medium · Dynamic Programming · Asked at Amazon, Microsoft, Paytm, Walmart
Count the ways to make the amount using unlimited coins of the given denominations. Order does not matter. Print the answer modulo 10^9 + 7.
Input
First line: n. Second line: n distinct denominations. Third line: amount.
Output
The number of ways modulo 1000000007.
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ coin ≤ 10^4
- 0 ≤ amount ≤ 10^4
Loop over coins in the outer loop so each combination is counted once.
Example 1
Input
3 1 2 5 5
Output
4
Example 2
Input
1 2 3
Output
0
Hints
- dp[x] = number of ways to make amount x; dp[0] = 1 (use no coins).
- Coins in the OUTER loop: for each coin c, for x from c up, dp[x] += dp[x − c]. Swapping the loops would count 1+2 and 2+1 separately.
Approach
Process coins one at a time. After handling coins c1..ck, dp[x] counts the multisets of those coins that sum to x. Adding coin c with dp[x] += dp[x − c] (x increasing, so c can be reused) extends each way with one more c. Every combination is built in a fixed coin order, so it's counted once. Take mod 10^9 + 7 at every addition.
Complexity: O(n · amount) time · O(amount) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
const long long MOD = 1000000007;
int n, amount;
cin >> n;
vector<int> coins(n);
for (auto &c : coins) cin >> c;
cin >> amount;
vector<long long> dp(amount + 1, 0);
dp[0] = 1;
for (int c : coins)
for (int x = c; x <= amount; x++) dp[x] = (dp[x] + dp[x - c]) % MOD;
cout << dp[amount] << "\n";
return 0;
}Python solution
import sys
MOD = 10**9 + 7
data = list(map(int, sys.stdin.read().split()))
n = data[0]
coins, amount = data[1 : n + 1], data[n + 1]
dp = [1] + [0] * amount
for c in coins:
for x in range(c, amount + 1):
dp[x] = (dp[x] + dp[x - c]) % MOD
print(dp[amount])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
final long MOD = 1000000007;
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();
long[] dp = new long[amount + 1];
dp[0] = 1;
for (int c : coins)
for (int x = c; x <= amount; x++) dp[x] = (dp[x] + dp[x - c]) % MOD;
System.out.println(dp[amount]);
}
}Solve Coin Change (Number of Ways) online · All practice problems