Coin Change

medium1D Dynamic Programming58 stepsJava · Python · C++

Find the fewest coins that make amount, with unlimited coins of each type. dp[a] is the fewest coins for amount a; for each coin c, dp[a] = min(dp[a], dp[a − c] + 1). Fill amounts from 0 upward.

▶ Watch the animated trace

Traced input: coins = [1, 3, 4], amount = 6 → 2. Original problem: neetcode.io/problems/coin-change

Complexity

BestO(S·k)

AverageO(S·k)

WorstO(S·k)

SpaceO(S)

S = amount, k = number of coin types.

Key idea

The last coin used was some c, leaving a − c to be made optimally.
Use amount + 1 as infinity: no answer can need that many coins.
If dp[amount] is still infinity, return -1.

Common mistakes

Greedy (largest coin first) fails: coins [1, 3, 4], amount 6 → greedy 4+1+1, best 3+3.
Using Integer.MAX_VALUE as infinity overflows when you add 1.

Solution

Java

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    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;
            }
        }
    }
    int result = dp[amount] > amount ? -1 : dp[amount];
    return result;
}

Python

def coinChange(coins: List[int], amount: int) -> int:
    dp = [amount + 1] * (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 -1 if dp[amount] > amount else dp[amount]

C++

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    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] > amount ? -1 : dp[amount];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Impossible Odd amounts can't be made from 2s.	`coins = [2], amount = 3`	`-1`
Amount 0 No coins needed.	`coins = [1], amount = 0`	`0`
Greedy would fail 3 + 3 beats 4 + 1 + 1.	`coins = [1, 3, 4], amount = 6`	`2`
Large coin only Exactly one coin.	`coins = [5], amount = 5`	`1`