Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

Coin Change (Fewest Coins)

Coin Change explained: why greedy fails and how a 1D DP table finds the fewest coins for an amount, with tested Python, common mistakes and a live DP visual.

Also searched as: coin change minimum coins · coin change dp · minimum number of coins to make an amount

🪙

Try it live Free

Coin Change (DP)

Watch dp[] fill left to right with each cell built from earlier answers, then compare against greedy overpaying and naive recursion exploding.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

You are given coin denominations (unlimited supply of each) and a target amount. Return the smallest number of coins that add up exactly to amount, or -1 if it cannot be made.

Inputcoins = [1, 2, 5], amount = 11
Output3

5 + 5 + 1

Inputcoins = [1, 3, 4], amount = 6
Output2

3 + 3. Greedy would pick 4 + 1 + 1 = 3 coins.

The key insight

The best way to make amount a ends with some last coin c, and what remains, a - c, must itself be made optimally. So dp[a] = 1 + min(dp[a - c]) over all coins. Fill the table from 0 upward and every answer you need is already there.

Brute force first: Recursion that tries every coin at every step explores an exponential tree, recomputing the same remaining amounts many times.

Step-by-step approach

  1. Create dp of size amount + 1, filled with infinity, and set dp[0] = 0.
  2. For each amount a from 1 to amount, try every coin c <= a.
  3. If dp[a - c] is reachable, update dp[a] = min(dp[a], dp[a - c] + 1).
  4. After the loop, dp[amount] is the answer; if it is still infinity, return -1.

Python solution

PYTHON 3tested
def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount        # dp[a] = fewest coins for amount a
    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

Complexity

TimeO(amount · k)
SpaceO(amount)

For each of the amount cells we try all k coins once. The table has one entry per amount.

Common mistakes

Frequently asked questions

What is the time and space complexity of Coin Change?

O(amount × number of coins) time and O(amount) space for the 1D table.

Why does the greedy approach fail for Coin Change?

Greedy commits to the largest coin without looking ahead. With coins 1, 3, 4 and amount 6, it takes 4 + 1 + 1 (three coins) while 3 + 3 needs only two.

What is the difference between Coin Change and Coin Change II?

Coin Change asks for the minimum number of coins (a min over choices). Coin Change II asks for the number of distinct combinations (a sum over choices), and its loop order must put coins on the outside to avoid counting the same combination twice.

Can Coin Change be solved with BFS?

Yes. Treat each amount as a node and each coin as an edge; BFS from 0 reaches the target in the fewest coins. It has the same worst-case cost as the DP.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.