Skip to content
RED SAGSkills
medium30 ptsdynamic-programming

Fewest Coins for an Amount

A vending machine has an unlimited supply of coins of each denomination in coins. Return the fewest coins needed to give exactly amount as change, or -1 if it cannot be done. Giving change for 0 needs 0 coins.

Note that always taking the largest coin first does not work for every set of denominations.

Example 1

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

Example 2

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

Constraints

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4
Hint 1

Let dp[a] be the fewest coins for amount a.

Hint 2

dp[a] = 1 + min(dp[a - c]) over every coin c that fits.

Discussion 0

Join free to post in the discussion.

Good practice for: Backend Developer, Full Stack Developer, Blockchain Developer, Data Scientist, Mobile App Developer

Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.