ALG-M015MediumDynamic Programming
Fewest Tokens for a Sum
Given positive coin denominations (unlimited supply of each), return the fewest coins needed to total amount exactly. Return -1 if impossible.
Contract
input coins: integer[]
input amount: integer
return integer
Constraints
- • All denominations > 0
- • 0 <= amount <= 10000
Examples
Example 1
coins = [1, 2, 5]
amount = 11
→ 3
Example 2
coins = [2]
amount = 3
→ -1
5 judge tests (2 shown above). Target complexity: O(amount * number_of_coins).