Dynamic Programming
LC #322Medium
Coin Change
Dynamic Programming
AmazonGoogleMetaBloombergMicrosoftProblem
Find the minimum number of coins needed to make up a given amount.
arraydynamic-programmingbfs
Constraints
- ›1 ≤ coins.length ≤ 12
- ›1 ≤ coins[i] ≤ 2³¹ − 1
- ›0 ≤ amount ≤ 10⁴
- ›Return -1 if impossible
Example
Input
coins = [1, 5, 6, 9], amount = 11Output
2Why
5+6=11 uses 2 coins. Not 1+1+9=11 (3 coins)