#4MediumDynamic Programming· Unbounded Knapsack

Coin Change

You have an unlimited supply of coins of each denomination listed in `coins`. Return the **fewest** coins whose values add up exactly to `amount`. If no combination of coins can make `amount`, return `-1`. Making an `amount` of `0` needs zero coins.

Input format

coins: array of distinct positive integers, amount: non-negative integer

Output format

Integer: minimum number of coins, or `-1` if the amount cannot be formed

Examples

Input: coins = [1, 3, 4], amount = 6

Output: 2

3 + 3 = 6 uses two coins. The greedy choice 4 + 1 + 1 would use three.

Input: coins = [2], amount = 3

Output: -1

Only even totals can be formed with 2-value coins, so 3 is impossible.

Input: coins = [1], amount = 0

Output: 0

An amount of 0 is already reached with no coins.

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
All values in `coins` are distinct.
0 <= amount <= 10^4

Study first

Dynamic Programming Patterns

#dynamic-programming
#arrays
#unbounded-knapsack
#breadth-first-search