Medium · Dynamic Programming

Coin Change

Given an array coins of positive denominations, each usable any number of times, and an integer amount, return the fewest coins that add up to exactly amount, or −1 if no combination does (amount 0 needs 0 coins).

Examples

Example 1

{
  "coins": [1, 3, 4],
  "amount": 6
}

Output: 2 coins

Example 2

{
  "coins": [2],
  "amount": 3
}

Output: no solution

Rebuild it in the studio

Core interview problems are free with a full runner and lessons; Pro opens the complete library.

More Dynamic Programming problems