Coin Change

Medium0/1 Knapsack (DP)Blind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an array coins of distinct coin denominations and an integer amount. You have an unlimited supply of every denomination. Return the fewest coins whose values add up to exactly amount, or -1 if no combination of coins reaches it. An amount of 0 needs 0 coins.

Examples

coins = [1,2,5], amount = 11 returns 3

5 + 5 + 1 = 11 uses three coins. Two coins top out at 5 + 5 = 10, so three is the minimum.

coins = [2], amount = 3 returns -1

Any number of 2s adds up to an even total, so 3 can never be reached.

coins = [1], amount = 0 returns 0

There is nothing to pay, so zero coins are needed.

Constraints

1 <= coins.length <= 12
0 <= amount <= 10^4

Hints

Hint 1

If you knew the minimum coins for every amount below the target, could you build up the answer?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Build a table dp where dp[a] is the fewest coins that make amount a. Start with dp[0] = 0 and every other entry at amount + 1, a stand-in for infinity, since no answer uses more than amount coins. For each a from 1 to amount, try every coin c <= a as the last coin: dp[a] = min(dp[a], dp[a - c] + 1). If dp[amount] is still above amount, it can't be made. O(amount * n) time, O(amount) space, n = number of coins.

Time

O(amount * n)

Space

O(amount)

Pitfall

Greedily taking the largest coin that fits fails: with coins [1,3,4] and amount 6, greedy picks 4 + 1 + 1 (three coins) while 3 + 3 needs only two. Use amount + 1 as the sentinel, not the max int, so dp[a - c] + 1 can't overflow.

Solutions

class Solution {
    public 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] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

class Solution:
    def coinChange(self, coins, 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:
                    dp[a] = min(dp[a], dp[a - c] + 1)
        return -1 if dp[amount] > amount else dp[amount]