Med.dynamic programming

Coin Change

Find the fewest coins that add up to a target amount.

Given coin denominations in coins and a target amount, return the fewest coins that sum to exactly amount. You have an unlimited supply of each denomination.

If no combination reaches the amount, return -1.

Constraints

  • 1 ≤ coins.length ≤ 12
  • 1 ≤ coins[i] ≤ 2³¹ - 1
  • 0 ≤ amount ≤ 10,000

Examples

Input
coins = [1,5,6,9], amount = 11
Output
2
Why
5 + 6. Greedy would take 9 first and need three coins.
Input
coins = [2], amount = 3
Output
-1
Why
Odd amount, even coin.
Input
coins = [1,2,5], amount = 11
Output
3
Why
5 + 5 + 1.

Submitting also runs 7 hidden tests.

Limits

2000 ms and 256 MB per test case.

You can run the examples without an account. Sign in to submit against the hidden cases and keep your progress.

Run checks the examples above. Submit checks those plus the hidden cases.