practice · medium · from Dynamic Programming

Coin Change

time: O(amount · |coins|)
space: O(amount)
tags: dynamic-programming

in the wild Cashier algorithms, transit-fare token minimization, network MTU packing, robot energy-budget step planning.

Problem

Given an array of integer coin denominations coins and an integer amount, return the fewest number of coins needed to make exactly amount. You may use each denomination any number of times. If the amount cannot be made, return -1.

Examples

coins = [1, 2, 5], amount = 11 → 3 (5 + 5 + 1)
coins = [2], amount = 3 → -1 (impossible)
coins = [1], amount = 0 → 0 (no coins needed)
coins = [1, 3, 4], amount = 6 → 2 (3 + 3, not greedy's 4+1+1=3)

The [1, 3, 4], 6 case is critical: the greedy "always take the largest coin ≤ remaining" gives 4 + 1 + 1 = 3 coins. The true optimum is 3 + 3 = 2 coins. Greedy fails on this kind of denomination set.

Why this is the canonical 1D unbounded-knapsack DP

The recurrence:

f(a) = 0                                       if a == 0
     = 1 + min over c in coins of f(a - c)      if any (a - c) is reachable
     = ∞ / -1                                   otherwise

In English: "the min coins to make a is one more than the min coins to make a − c, taken over the best coin c."

This is unbounded knapsack in disguise — each coin can be used any number of times. The state space is just a ∈ [0, amount] (a 1D table), and the transition examines every coin. Total work: O(amount × |coins|).

Why is greedy wrong, and why does DP fix it? Greedy commits to a local choice that's hard to back out of when a future obstacle appears. DP enumerates every possible last-coin choice for every amount, so it never gets pinned. That's the universal DP advantage: brute-force every choice, but cache the work.

The same recurrence shape solves: "min steps to make amount", "min items to fit weight", "longest divisible chain", "perfect squares decomposition", "make N with given operations".

Hints

Hint 1 — what's the state?

The answer for amount = 11 depends only on amount, not on which coins you've used so far (since coins are unbounded). So state is a single integer a ∈ [0, amount]. What's f(a) in terms of f(smaller values)?

Hint 2 — try each coin as "the last one used"

For any target a, the last coin you placed was some c ∈ coins (and that coin made a - c into a). So f(a) = 1 + min over c of f(a - c), but only over coins c where a - c ≥ 0 and f(a - c) is reachable.

Hint 3 — table filling order

Compute f(0), f(1), f(2), …, f(amount) in order. Use ∞ as a sentinel for "not yet reachable"; convert to -1 at the end if f(amount) is still ∞.

Solution

def coin_change(coins: list[int], amount: int) -> int:
    INF = amount + 1                          # any value > amount works as ∞
    dp  = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

cases = [
    ([1, 2, 5],   11,  3),
    ([2],          3, -1),
    ([1],          0,  0),
    ([1, 3, 4],    6,  2),                    # the greedy-defeats case
    ([186, 419, 83, 408], 6249, 20),
]
for coins, amount, expected in cases:
    got  = coin_change(coins, amount)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} coin_change({coins}, {amount}) = {got}  (expected {expected})")

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

const cases = [
  [[1, 2, 5],          11,  3],
  [[2],                 3, -1],
  [[1],                 0,  0],
  [[1, 3, 4],           6,  2],
  [[186, 419, 83, 408], 6249, 20],
];
for (const [coins, amount, expected] of cases) {
  const got = coinChange(coins, amount);
  console.log(`${got === expected ? "✓" : "✗"} coinChange(${JSON.stringify(coins)}, ${amount}) = ${got}  (expected ${expected})`);
}

pub fn coin_change(coins: &[i32], amount: i32) -> i32 {
    let amount = amount as usize;
    let inf    = amount + 1;
    let mut dp = vec![inf; amount + 1];
    dp[0] = 0;
    for a in 1..=amount {
        for &c in coins {
            let c = c as usize;
            if c <= a && dp[a - c] + 1 < dp[a] {
                dp[a] = dp[a - c] + 1;
            }
        }
    }
    if dp[amount] == inf { -1 } else { dp[amount] as i32 }
}

fn main() {
    let cases: Vec<(&[i32], i32, i32)> = vec![
        (&[1, 2, 5][..],            11,  3),
        (&[2][..],                   3, -1),
        (&[1][..],                   0,  0),
        (&[1, 3, 4][..],             6,  2),
        (&[186, 419, 83, 408][..], 6249, 20),
    ];
    for (coins, amount, expected) in cases {
        let got  = coin_change(coins, amount);
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} coin_change({:?}, {}) = {}  (expected {})", coins, amount, got, expected);
    }
}

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

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

int main() {
    struct Case { std::vector<int> coins; int amount; int expected; };
    std::vector<Case> cases = {
        { {1, 2, 5},   11,  3 },
        { {2},          3, -1 },
        { {1},          0,  0 },
        { {1, 3, 4},    6,  2 },
        { {186, 419, 83, 408}, 6249, 20 },
    };
    for (auto& c : cases) {
        int got = coin_change(c.coins, c.amount);
        std::cout << (got == c.expected ? "✓" : "✗")
                  << " coin_change(.., " << c.amount << ") = " << got
                  << "  (expected " << c.expected << ")\n";
    }
}

#include <stdio.h>
#include <stdlib.h>

int coin_change(const int* coins, int n_coins, int amount) {
    int INF = amount + 1;
    int* dp = malloc((amount + 1) * sizeof(int));
    for (int i = 0; i <= amount; i++) dp[i] = INF;
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int i = 0; i < n_coins; i++) {
            int c = coins[i];
            if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
        }
    }
    int ans = dp[amount] == INF ? -1 : dp[amount];
    free(dp);
    return ans;
}

int main(void) {
    int a1[] = {1, 2, 5};         printf("%s coin_change([1,2,5], 11) = %d\n",
                                    coin_change(a1, 3, 11) == 3  ? "✓" : "✗", coin_change(a1, 3, 11));
    int a2[] = {2};               printf("%s coin_change([2], 3) = %d\n",
                                    coin_change(a2, 1, 3)  == -1 ? "✓" : "✗", coin_change(a2, 1, 3));
    int a3[] = {1};               printf("%s coin_change([1], 0) = %d\n",
                                    coin_change(a3, 1, 0)  == 0  ? "✓" : "✗", coin_change(a3, 1, 0));
    int a4[] = {1, 3, 4};         printf("%s coin_change([1,3,4], 6) = %d\n",
                                    coin_change(a4, 3, 6)  == 2  ? "✓" : "✗", coin_change(a4, 3, 6));
    int a5[] = {186,419,83,408};  printf("%s coin_change(..,6249) = %d\n",
                                    coin_change(a5, 4, 6249) == 20 ? "✓" : "✗", coin_change(a5, 4, 6249));
    return 0;
}

idle

The whole problem collapses to a double loop: outer a from 1 to amount, inner over coins. Five lines of actual algorithm; the rest is bookkeeping.

Complexity

Time: O(amount × |coins|) — each cell of the dp table examines every coin.
Space: O(amount) — the 1D table. Cannot be space-optimized further for this recurrence (every prior cell may be the source).
Greedy (when it works): O(amount / max-coin) — but only correct for "canonical" coin systems (like USD: 1/5/10/25 cents). Arbitrary coin sets need DP.

In the wild

Cashier algorithms in commerce systems with non-canonical denominations (some currencies, transit-fare tokens, voucher systems).
Network MTU packing. Splitting payloads into the fewest fragments under fixed allowed sizes.
Robot energy budgeting. "Reach distance d using fewest 'big-power' / 'small-power' steps, given step costs."
Compiler instruction selection. Synthesize a target value using fewest instructions from an allowed instruction set.

Variations

Coin Change II — count the number of ways to make amount, not the minimum coins. Recurrence becomes f(a) = sum over c of f(a - c), with care to avoid double-counting orderings (outer loop coins, inner loop amount).
Unbounded knapsack. Items with weight + value; maximize value within capacity W. Same O(W·n) shape.
Bounded coin change — each coin can be used at most k times. 2D state (amount, coin-index) or "0/1 knapsack" treatment.
Make change with specific denominations only printed once. A DP variant; reset which coins are usable per step.