Dynamic Programming
LC #518Medium
Coin Change II
Dynamic Programming
AmazonGoogleMetaBloombergProblem
Count the number of combinations of coins that make up the amount (unlimited coins of each denomination).
arraydynamic-programming
Constraints
- ›1 ≤ coins.length ≤ 300
- ›1 ≤ coins[i] ≤ 5000
- ›0 ≤ amount ≤ 5000
- ›Answer guaranteed to fit in a 32-bit integer
Example
Input
amount = 5, coins = [1, 2, 5]Output
4Why
5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1 → 4 ways