Coin Change (Count Ways)
Hard · rating 1800 · Dynamic Programming
The first line contains n and an amount A. The second line has n distinct positive coin values (unlimited supply of each). Print the number of distinct multisets of coins that sum to exactly A.
Constraints: 1 ≤ n ≤ 50, 0 ≤ A ≤ 5000
Editorial
Approach
This is the classic unbounded-knapsack counting DP. Let dp[a] be the number of ways to make amount a. Process the coins one at a time in the outer loop — this counts each multiset once, since coins are only ever added in a fixed order.
The ordering trick
Iterating coins outside and amounts inside means a solution using coin 5 then coin 2 is never counted separately from 2 then 5 — combinations, not permutations.
dp = [0] * (A + 1); dp[0] = 1
for coin in coins:
for a in range(coin, A + 1):
dp[a] += dp[a - coin]
return dp[A]Complexity
Time: O(n·A). Space: O(A).
Related problems
- 0/1 Knapsack — Hard
- Edit Distance — Hard
- Minimum Path Sum — Hard
- Minimum Subset Difference — Hard
- Word Break — Hard
- Coin Change — Hard