jsschools

Coin Change Problem

Finds the minimum number of coins from a given set of denominations that sum to a target amount, using bottom-up dynamic programming (unbounded knapsack variant).

Spec ↗

Syntax

coinChange(coins, amount)

Parameters

NameTypeRequiredDescription
coins number[] Yes Array of distinct coin denominations (positive integers).
amount number Yes Target sum to achieve. Non-negative integer.

Returns

number — Minimum number of coins, or -1 if the amount cannot be formed.

Examples

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

console.log(coinChange([1, 5, 6, 9], 11));
console.log(coinChange([2], 3));
Output 
2
-1

// Count the number of ways to make the amount (coin change II)
function coinChangeWays(coins, amount) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {
      dp[a] += dp[a - coin];
    }
  }
  return dp[amount];
}

console.log(coinChangeWays([1, 2, 5], 5));
Output 
4

Notes

| Case | Time | Space | |---------|-----------|-------| | Best | O(n·W) | O(W) | | Average | O(n·W) | O(W) | | Worst | O(n·W) | O(W) | where n = number of coin types and W = amount. The DP builds up from dp[0] = 0. Coins can be reused (unbounded), so inner loop goes left-to- right. Coin Change II (counting ways) iterates coins in the outer loop to avoid counting the same combination multiple times (order-insensitive). The greedy algorithm (always take the largest coin ≤ remaining) does NOT always give the optimal solution (e.g. coins [1,5,6,9], amount 11 — greedy gives 9+1+1=3 coins, DP gives 6+5=2 coins).

See also