Coin Change

Dynamic Programming, problem 4 of 9

Coin Change

Medium

LC #322

unbounded knapsack1d dp

Not attempted yet

You have coins of the values in coins, with an unlimited supply of each. Return the fewest coins that add up to exactly amount, or -1 if it can't be done.

Example 1

Input: coins = [1, 2, 5], amount = 11
Output: 3
5 + 5 + 1

Example 2

Input: coins = [2], amount = 3
Output: -1

Example 3

Input: coins = [1], amount = 0
Output: 0

Constraints

  • 1 ≤ len(coins) ≤ 12
  • 1 ≤ coins[i] ≤ 2³¹ - 1
  • 0 ≤ amount ≤ 10⁴

Python

Loading draft…

Test results

8 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 5 hidden

Run examples, then submit all tests.