Coin Change

You have an unlimited supply of coins of a few different values, and you want to pay an exact amount using as few coins as you can.

Grabbing the biggest coin that still fits sounds right, but it can fail. With coins [1, 3, 4] and an amount of 6, the biggest coin first gives 4 + 1 + 1, three coins, while 3 + 3 needs only two.

A safer way is to build the answer up from small amounts. Let fewest[t] be the fewest coins that add up to t. Paying 0 takes no coins. For any other t, the last coin you use has some value c, and what is left before it is t - c, so

fewest[t] = 1 + the smallest fewest[t - c] over every coin c that is not bigger than t.

For [1, 3, 4]: fewest[3] = 1, and fewest[6] = 1 + fewest[3] = 2. If no coin leads to a reachable amount, t cannot be paid at all.

Write a function named coinChange that gets coins, a list of distinct coin values, and an integer amount, and returns the fewest coins that add up to exactly amount. Each coin value can be used as many times as you like. Return -1 if the amount cannot be made, and 0 when amount is 0.

For example, coins = [2, 5, 10] and amount = 27 returns 4 (10 + 10 + 5 + 2), and coins = [4, 6] with amount = 7 returns -1.

Constraints: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, all values distinct, 0 <= amount <= 10^4.