Recursion - Data Structures and Problem Solving Using Java - page 332

figure 7.24
An alternative
recursive algorithm for
the coin-changing
problem

1 + 21 21 10

10

5 + 25 21 10

1 1

10 21 21 10 1

+

21 21 21

+

25 25 10 1 1 1

+

solves for 52 cents. In the third case we are left with 53 cents. One of its recursive
calls removes the 1-cent piece and also recursively solves for 52 cents. This
redundant work again leads to excessive running time. If we are careful, how-
ever, we can make the algorithm run reasonably fast.
The trick is to save answers to the subproblems in an array. This dynamic
programming technique forms the basis of many algorithms. A large answer
depends only on smaller answers, so we can compute the optimal way to
change 1 cent, then 2 cents, then 3 cents, and so on. This strategy is shown in
the method in Figure 7.25.
First, at line 8 we observe that 0 cents can be changed using zero coins.
The lastCoin array is used to tell us which coin was last used to make the opti-
mal change. Otherwise, we attempt to make cents worth of change, for cents
ranging from 1 to the final maxChange . To make cents worth of change, we try
each coin in succession as indicated by the for statement beginning at line 15.
If the amount of the coin is larger than the amount of change we are trying to
make, there is nothing to do. Otherwise, we test at line 19 to determine
whether the number of coins used to solve the subproblem plus the one coin
combine to be fewer than the minimum number of coins used thus far; if so,
we perform an update at lines 21 and 22. When the loop ends for the current
number of cents , the minimums can be inserted in the arrays, which is done at
lines 26 and 27.
At the end of the algorithm, coinsUsed[i] represents the minimum number of
coins needed to make change for i cents ( i==maxChange is the particular solution
that we are looking for). By tracing back through lastCoin , we can figure out the
coins needed to achieve the solution. The running time is that of two nested
for loops and is thus O ( NK ), where N is the number of different denomina-
tions of coins and K is the amount of change that we are trying to make.