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

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.