32Coin Change

Harddynamic programming

Write min_coins(coins, amount) that returns the smallest number of coins needed to make exactly amount, using any number of each coin value in coins.

If the amount can't be made, return -1. Making 0 needs 0 coins.

Examples

Example 1

>>> min_coins([1, 2, 5], 11)
3

Example 2

>>> min_coins([2], 3)
-1

Good to know

Always taking the biggest coin first does not always work: with coins [1, 3, 4] and amount 6, the best answer is 3 + 3, not 4 + 1 + 1.

Run examples checks the 2 examples above. Submit runs all 7 tests, including hidden edge cases, and marks the challenge solved.