Coin Change

Problem

Given unlimited coins of the listed denominations and a target amount, return the fewest coins needed to make the amount, or -1 if it is impossible.

Use bottom-up dynamic programming where dp[x] is the minimum coins for value x, initialised with a sentinel larger than any real answer, and return 0 for amount 0.

Hint

For each coin, sweep amounts upward so the coin can be reused.

Test cases

case 1

in: [[1,2,5],11]

expected: 3

case 2

in: [[2],3]

expected: -1

case 3

in: [[1],0]

expected: 0

case 4

in: [[2,5,10,1],27]

expected: 4

case 5

in: [[],0]

expected: 0

Starter codePython

def coin_change(coins, amount):
    # Your code here
    pass

5 test cases · run your code against them in the editor