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

Coin Change: Number of Ways

Count distinct ways to make change for a target amount with given coin denominations.

Coin Change: Number of Ways

You'll learn how to count all the distinct ways to make exact change for a target amount using unlimited coins of given denominations.

The Core Problem

Imagine you need to make exactly $5 using quarters (25¢), dimes (10¢), and nickels (5¢). How many different combinations can you use? You could use 20 nickels, or 10 nickels + 5 dimes, or 2 dimes + 3 nickels + 1 quarter, and so on.

Unlike the "Minimum Coins" variant (which finds the fewest coins needed), this problem asks: in how many distinct ways can we combine coins to reach our target?

Why Dynamic Programming?

This problem has both key DP properties:

  1. Optimal substructure: To count ways to make amount n with coins [c1, c2, ...], we can break it down: ways using coin c1 + ways not using c1.

  2. Overlapping subproblems: When counting ways to make 5,you′llrepeatedlyneedtoknowwaystomake5, you'll repeatedly need to know ways to make 3, $2, etc.

The State and Transition

Define dp[amount][coin_index] = number of ways to make amount using only the first coin_index coin types.

Recurrence:

  • If we don't use the current coin: dp[amount][coin_index - 1]
  • If we do use it: dp[amount - coin_value][coin_index] (we can use it again!)

Sum both possibilities.

Base case: There's exactly 1 way to make amount 0 (use no coins).

Space-Optimized Approach

You can reduce to a 1D array: dp[i] = ways to make amount i. Process each coin and update all reachable amounts.

Key Takeaway: Count combinations by deciding whether to include/exclude each coin denomination, summing ways from overlapping subproblems using DP to avoid redundant calculations.