Mid · Dynamic programming

Fewest Coins for an Amount

Given distinct positive integer coin values and an amount from 0 to 50, return the minimum coin count using unlimited copies, or -1 when impossible. A greedy choice is not always optimal. Use small amounts such as 6 to compare the recursive baseline; its exponential cost makes even some inputs within this range impractical.

Examples

[1,3,4], 6 → 2

Compare approaches

Exhaustive recursion

Try every legal next coin. Repeated subproblems make this unsuitable for large amounts. k is the number of denominations; A is the amount.

Time: O((k + 1)^A) loose upper bound · Space: O(A) recursion depth

function fewestCoins(coins, amount) { function visit(left) { if (left === 0) return 0; let best = Infinity; for (const coin of coins) if (coin <= left) best = Math.min(best, 1 + visit(left - coin)); return best; } const answer = visit(amount); return Number.isFinite(answer) ? answer : -1; }

Bottom-up dynamic programming

Store the best answer for each smaller amount exactly once; positive coins guarantee the dependency is already computed.

Time: O(k × A) · Space: O(A)

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

Common traps

Zero or negative coins invalidate this recurrence.
Infinity represents unreachable, not zero.

Practise in the workspace →