python - 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]