Coding

Coin Change

Dynamic programming · Medium

Dynamic programmingMedium

Overview

Coin Change: find the fewest coins that sum to a target amount. A bottom-up DP over every amount from 0 to target computes the minimum, reusing smaller subresults, and returns -1 when the amount is unreachable.

How it works

Dynamic programming

ClientServiceDataEdge

Step by step, with examples

1
dp[amount]
- Min coins to make each amount.
2
dp[0]=0
- Zero coins make zero; init others to ∞.
3
Fill table
- dp[a] = min(dp[a−c] + 1) bottom-up.
4
dp[amount]
- Return it, or −1 if unreachable.
- Example: amount 11 → 3

Problem

Given coin denominations and an amount, return the fewest coins needed to make that amount, or -1 if impossible.

Approach

dp[x] = min coins to make x, init Infinity, dp[0]=0
For each amount, try every coin

Solution

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

Complexity

Time O(amount · coins), Space O(amount).

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions