Coin Change

Approach Summary

dp[i] = min coins to make amount i. For each amount, try all coins: dp[i] = min(dp[i], dp[i - coin] + 1).

Full Solution & Approach

Let dp[a] be the minimum number of coins needed to make amount a, with dp[0] = 0 and everything else initialized to a large sentinel. For each amount from 1 to the target, try every coin: if a coin is usable, dp[a] = min(dp[a], dp[a - coin] + 1). This is an unbounded knapsack in 1D — because coins can be reused, the natural iteration order (amount ascending, coins nested) allows each coin to be used any number of times. After the loop, if dp[target] is still the sentinel, the amount is unreachable and the answer is -1. The recurrence is O(amount × n) with n coins. Two alternative views: BFS on amounts with coin edges gives the same complexity, and the greedy largest-coin-first strategy fails in general — the DP is the reliable approach.

Two nested loops over amount and coins — O(amount × number_of_coins) time. A single dp array of size amount + 1 — O(amount) space.

Solution Code

Solution

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

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

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a && dp[a - c] != Integer.MAX_VALUE) {
                dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

int coinChange(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a && dp[a - c] != INT_MAX) {
                dp[a] = min(dp[a], dp[a - c] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

Edge Cases to Watch

Amount 0 — return 0 (zero coins)
Amount not representable — return -1
A coin worth more than the amount — skipped naturally
Duplicate coin denominations — harmless

How to Recognize This Pattern

Minimum coins to make amount
Unbounded knapsack

Complexity Analysis

Time Complexity

O(amount × n)

Space Complexity

O(amount)