Problem statement

Given coin denominations coins (infinite supply of each) and a total amount, return the fewest coins needed to make up that amount, or -1 if it cannot be made.

Example 1

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 5 + 5 + 1.

Example 2

Input: coins = [2], amount = 3
Output: -1

Example 3

Input: coins = [1], amount = 0
Output: 0

Constraints

• 1 <= coins.length <= 5
• 1 <= coins[i] <= 25
• 0 <= amount <= 100

Hints for Coin Change

1. Hint 1

   dp[a] = fewest coins for amount a; build up from 0.

2. Hint 2

   dp[a] = 1 + min(dp[a - c]) over all usable coins c.

How to solve Coin Change

Work upwards through every amount from 1 to the target. To make amount a, the last coin used was some c, leaving the subproblem a - c — already solved. So best[a] = 1 + min(best[a - c]) over all coins that fit. This is an unbounded knapsack, and building it bottom-up means each amount is solved once.

Approach

1. Create a table best[0 .. amount], filled with a sentinel meaning "unreachable", and set best[0] = 0.
2. For each amount a from 1 upwards, try every coin c that is at most a.
3. If a - c is reachable, consider best[a - c] + 1 and keep the smallest.
4. After the sweep, return best[amount], or -1 if it is still unreachable.

Why it works

Every way of making a ends with some coin, and removing that coin leaves a valid — and independently optimal — way of making a - c; if it were not optimal you could substitute a better one and improve a. That is optimal substructure. Sweeping amounts in increasing order guarantees every a - c is final before a is computed, and because coins may repeat, a - c may itself already use c — which is exactly what unbounded reuse requires.

Complexity

• Time — O(amount · coins)
• Space — O(amount)

Pitfalls

• Distinguish unreachable from zero. A sentinel like amount + 1 works because no valid answer can exceed amount.
• Guard a - c >= 0 before indexing.
• Greedy — always taking the largest coin — is wrong here: with coins [1, 3, 4] and amount 6 it gives 3 coins instead of 2.
• amount = 0 must answer 0, which the base case handles.

Reference solution

Python

from typing import List

def coinChange(coins: List[int], amount: int) -> int:
    INF = float("inf")
    dp = [0] + [INF] * amount
    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] == INF else dp[amount]

Java

public static int coinChange(int[] coins, int amount) {
    int INF = amount + 1;
    int[] best = new int[amount + 1];
    Arrays.fill(best, INF);
    best[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a && best[a - c] + 1 < best[a]) best[a] = best[a - c] + 1;
        }
    }
    return best[amount] > amount ? -1 : best[amount];
}

C++

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

JavaScript

var coinChange = function(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 - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium