Making change using dynamic programming

Problem:

Consider the problem of making change. Assume coins of values 25 cents (i.e., a quarter), 10 cents (dime), 5 cents (nickel), and 1 cent (penny). Suppose now we want to return 63 cents in change. What would you do?

Now suppose that our coins’s values are instead: 1 cent, 5 cents, and 11 cents. We want to make change of 15 cents. Can you apply the same method as what you did above?

Follow-Up:

We can use a greedy method to find the smallest number of coins required for the first case:

63 (divide) 25 = 2         remainder =13
13 (divide) 10 = 1         remainder = 3

Thus, we need two quarters, one dime, and three pennies.

However, it is easy to see that the greedy method does not work for the second case. Indeed, we end up using one 11 cents and four 1 cent, while in fact three 5 cents would do good.

The lesson, again, is that greedy method does not always work.

Some of you discovered solving the second case using a “recursive” idea:

f(15) = min { f(14), f(10), f(4) } + 1

where f(n) denotes the minimum number of coins needed to make change for n cents.

The rationale of the above “recursive” idea is that the first term inside the “min” represents the case where one 1 cent coin is used so that we still need to make change for 14 cents. Similarly, the second term represents the case where one 5 cents coin is used so that we still need to make change for 10 cents. Finally, the third term represents the case where one 11 cents coin is used so that we still need to make change for 4 cents.

To really compute the answers, we need to further “reduce” the problems on the right side of the above equation (called a recurrence equation), until we get to the trivial cases, e.g., f(1), f(5), f(11) .

In fact, to construct the final answer, we need to build it from “bottom-up”, i.e., at the beginning we use the trivial cases, and then construct the bigger cases, and so on, until we get to the original question.

There is an official name for this “bottom-up” construction of recursively defined solutions—dynamic programming. This is a very powerful algorithm design paradigm that can be applied in solving many problems.

Further Inquiry:

(a) What is the estimated running time of the above dynamic programming method?
(b) Can you find a general relationship for the coin denominations so that the greedy method is optimal?