liveBook · Manning

Change-making problem

As explained in Timeless Algorithms, The Foundational Ideas

The coin change problem is the computational problem of determining ways to form a target amount from a specified set of coin denominations, typically with a counting or optimization objective.

The change-making problem asks how to form a target amount from fixed coin denominations. One version minimizes the number of coins; another counts distinct combinations, treating different orders of the same coins as one solution. section 6.3

For counting, dynamic programming processes denominations one at a time. Initialize ways[0] = 1 and other amounts to zero; for each coin c, add ways[n − c] to ways[n] when n ≥ c. This counts combinations without counting coin orderings separately. section 6.3 section 6.3.5

Counting ways to make 12

With denominations {1, 5, 10}, tabulation updates the counts as each denomination is added. After processing all three, ways[12] = 4. section 6.3.5

Table 6.10 Counts after adding the 10-unit coin. Processing the final denomination increases the counts for amounts 10 through 12, producing ways[12] = 4.
𝑛
0
1
2
3
4
5
6
7
8
9
10
11
12
After 𝑐 = 10
1
1
1
1
1
2
2
2
2
2
4
4
4

The table shows the counts after processing each denomination and the final value for 12. section 6.3.5

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Works through base values and denomination updates for a target of 12, without detailing implementation beyond tabulation.
Examples
Counts combinations for target 12 using denominations 1, 5, and 10, including intermediate counts after adding coins.
What you can do after
Understand how denomination-by-denomination tabulation counts combinations without treating different coin orders as distinct.
How it connects
Connects dynamic programming and knapsack through shared problem structure and formulation, while distinguishing counting from optimization.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.