Fewest Coins for an Amount

MediumArraysDynamic programming263 tests

You get an array coins of different positive coin values and a non-negative integer amount.

You have an unlimited number of coins of each value. Return the fewest coins whose values add up to exactly amount. If no mix of coins makes that amount, return -1.

Note

If amount is 0, the answer is 0: you use no coins.

Hint

Taking the largest coin first does not always give the fewest coins. Instead, find the answer for every amount from 0 up to amount. For each amount, try every coin as the last coin used.

Examples

Example 1

Input:: [1,6,10], 12
Output:: 2

6 + 6 = 12 uses 2 coins. Taking 10 first gives 10 + 1 + 1, which uses 3 coins.

Example 2

Input:: [4,10], 7
Output:: -1

Both coin values are even, so every total is even. 7 cannot be made.

Example 3

Input:: [3,8], 0
Output:: 0

An amount of 0 needs no coins.

Constraints

1 <= coins.length <= 6
1 <= coins[i] <= 60, and all values in coins are different.
0 <= amount <= 300

Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.