#295 Coin Change

medium
javascript
blind75
dynamic-programming

Given:

  • An array of coin denominations coins
  • A target amount amount
  • Unlimited supply of each coin

Return the minimum number of coins needed to make up the exact amount. Return -1 if impossible.

Constraints:

  • 1 ≤ coins.length ≤ 10
  • 1 ≤ coins[i] ≤ 2^31 - 1
  • 0 ≤ amount ≤ 10000

Examples:

// Example 1:
console.log(coinChange([1, 5, 10], 12));
// Output: 3
// Explanation: 12 = 10 + 1 + 1

// Example 2:
console.log(coinChange([2], 3));
// Output: -1
// Explanation: Can't make 3 with only 2's

// Example 3:
console.log(coinChange([1], 0));
// Output: 0
// Explanation: No coins needed for 0