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
