Dynamic Programming Optimal Coin Change

Question

I've been reviewing some dynamic programming problems, and I have had hard time wrapping my head around some code in regards to finding the smallest number of coins to make change.

Say we have coins worth 25, 10, and 1, and we are making change for 30. Greedy would return 25 and 5(1) while the optimal solution would return 3(10). Here is the code from the book on this problem:

def dpMakeChange(coinValueList,change,minCoins):
   for cents in range(change+1):
      coinCount = cents
      for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
      minCoins[cents] = coinCount
   return minCoins[change]

If anyone could help me wrap my head around this code (line 4 is where I start to get confused), that would be great. Thanks!

Answer 1

It looks to me like the code is solving the problem for every cent value up until target cent value. Given a target value v and a set of coins C, you know that the optimal coin selection S has to be of the form union(S', c), where c is some coin from C and S' is the optimal solution for v - value(c) (excuse my notation). So the problem has optimal substructure. The dynamic programming approach is to solve every possible subproblem. It takes cents * size(C) steps, as opposed to something that blows up much more quickly if you just try to brute force the direct solution.

def dpMakeChange(coinValueList,change,minCoins):
   # Solve the problem for each number of cents less than the target
   for cents in range(change+1):

      # At worst, it takes all pennies, so make that the base solution
      coinCount = cents

      # Try all coin values less than the current number of cents
      for j in [c for c in coinValueList if c <= cents]:

            # See if a solution to current number of cents minus the value
            # of the current coin, with one more coin added is the best 
            # solution so far  
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1

      # Memoize the solution for the current number of cents
      minCoins[cents] = coinCount

   # By the time we're here, we've built the solution to the overall problem, 
   # so return it
   return minCoins[change]

Answer 2

Here is a way to think about the coin changing problem that may be useful, if you are comfortable with graph theory.

Assume you have a graph defined in the following way:

• There is one node for every unit of money (e.g., pennies) from 0 up to the value you are interested in (e.g., 39 cents, or whatever.)
• There is one arc between any two nodes separated by exactly the value of a coin you are allowed to use (e.g., a node between 34 cents and 29 cents if you are allowed to use nickels.)

Now you can think of the coin changing problem as a shortest path problem from your value of interest down to zero, because the number of coins will be exactly the same as the number of arcs in your path.

The algorithm doesn't use a graph theory terminology, but it is doing basically the same thing: The outer loop is ranging over all the "cents" (or nodes, in the graph theory framework) and the inner loop is ranging over all the arcs (the values in coinValueList) from the present arc to the next arc. All together, they are looking for the shortest path from zero up to your value of interest. (Value down to zero, zero up to value, doesn't matter. Traditionally we search downward to zero, though.)

I only really started to understand dynamic programming when I realized many problems could be cast as graph problems. (Be careful, though-- not all of them can. Some are hypergraphs, and some are probably not even that. But it helped me a lot.)