Fewest Coupons to Reach an Amount

Mediumdynamic programming 00:00

Coupons come in denominations coins (unlimited supply). Return the fewest coupons that sum to exactly amount, or -1 if impossible.

fewestCoupons(coins: int[], amount: int) → int

Example 1

coins = [1,2,5]

amount = 11

output = 3

5 + 5 + 1

Example 2

coins = [2]

amount = 3

output = -1

-1

Example 3

coins = [1]

amount = 0

output = 0

⌘/Ctrl + Enter runs examples

Run checks the examples. Submit runs every hidden test (18, including large inputs that catch slow solutions).