Course contentsShow
← Computer Science
Lesson 928 of 2,87222. Dynamic ProgrammingFree lesson

Coin Change: Minimum Coins

Find the minimum number of coins needed to make a target amount using unbounded knapsack DP.

Coin Change: Minimum Coins

You'll learn how to find the fewest coins needed to make exact change using dynamic programming.

The Problem

Imagine you're a cashier with unlimited coins of certain denominations (like 1¢, 5¢, 10¢, 25¢). A customer needs exact change for a specific amount. What's the minimum number of coins you can use?

This is the Coin Change problem, and it's a classic application of dynamic programming that builds on the unbounded knapsack pattern.

Why Dynamic Programming?

This problem has optimal substructure: if you know the minimum coins for amount n-1, you can build the solution for n. It also has overlapping subproblems: calculating the answer for different amounts reuses smaller subproblem solutions.

The greedy approach (always picking the largest coin) doesn't always work. For coins [1, 3, 4] and amount 6, greedy gives 4+1+1 = 3 coins, but optimal is 3+3 = 2 coins.

The DP Approach

Define your state: dp[i] = minimum coins needed to make amount i.

Base case: dp[0] = 0 (zero coins for zero amount).

Transition: For each amount i, try using each coin c:

  • If c ≤ i, then dp[i] = min(dp[i], dp[i-c] + 1)
  • The +1 counts the coin you just used

This is "unbounded" because you can reuse the same coin denomination multiple times.

You build the table from amount 1 up to your target, considering all coin options at each step.

Key Takeaway: The Coin Change problem uses bottom-up DP to try each coin at every amount, tracking the minimum count by building on previously solved subproblems—a perfect example of optimal substructure with overlapping subproblems.