mediumDynamic programming, 1D target 25 min
Fewest coins
You have as many coins as you like of each value in coins, and you need to pay exactly amount. Find the smallest number of coins whose values add up to amount and return that number. When no mix of coins adds up to amount exactly, return -1. Paying 0 takes no coins, so an amount of 0 gives 0.
Example 1
Input
coins = [1, 4, 5], amount = 8Output24 + 4. Taking the biggest coin first gives 5 + 1 + 1 + 1, which is 4 coins.
Example 2
Input
coins = [3, 7], amount = 5Output-1One 3 leaves 2, which no coin pays, and two 3s or one 7 are already more than 5.
Example 3
Input
coins = [2, 5], amount = 11Output45 + 2 + 2 + 2. Two 5s make 10, and no coin pays the last 1.
Constraints
1 ≤ len(coins) ≤ 12
1 ≤ coins[i] ≤ 109, and no value appears twice
0 ≤ amount ≤ 104
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.