Coin Change | Problems

Given coins of different denominations and a total amount, return the fewest coins needed to make up that amount. Return -1 if not possible.

Example: coins = [1,2,5], amount = 11 → Output: 3 (5+5+1)

Sample Input

—

Sample Output

—

Constraints

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

Test Cases

Case 1

Args: [[1,2,5],11] Expected: 3

Case 2

Args: [[2],3] Expected: -1

Case 3

Args: [[1],0] Expected: 0

Topics

Dynamic Programming Memoization

Bottom-Up DP

dp[i] = minimum coins for amount i.

function coinChange(coins, amount) {
  const dp = Array(amount + 1).fill(amount + 1);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

Time: O(amount × coins) | Space: O(amount)

Saved in this browser only. Private to you.