Dynamic programming and induction

In this post we’ll talk about a common example in dynamic programming and how it relates to inductive definitions in math.

The problem

We want to write a program that tells us the smallest number of coins needed to make up each value under $1.00. We will assume we have access to as many coins as we need from a small set of denominations.

For example, suppose we can use coins with values $0.01 (pennies), $0.05 (nickels), $0.10 (dimes), and $0.25 (quarters). If we want to make $0.07, we can use 7 pennies, or we could use 1 nickel and 2 pennies. If we want to use the smallest number of coins, then we’ll use the 1 nickel and 2 pennies, which is 3 coins. In this case, our program should tell us that we can make $0.07 with just 3 coins.

For larger values like $0.28, there are many other options to consider. We could use 28 pennies, or 5 nickels and 3 pennies, or 2 dimes and 8 pennies, or 2 dimes 1 nickel and 3 pennies, etc. If we listed out the options, eventually we would see that we can use 1 quarter and 3 pennies, for a total of 4 coins. In this case, our program should tell us that we can make $0.28 with just 4 coins.

We want our program to give us a list telling us, for each value under $1.00, the smallest number of coins needed.

A naive solution

The most straightforward way to solve this would be to continue like in the above examples. We could look at each value, list out all the combinations of coins that add that value, and then select the minimal number of coins we saw.

However, doing this would be very repetitive. As we look at larger values, we would start to notice that we keep considering similar combinations of coins. Many of these combinations would be pointless to look at, as well. For example, once we know that $0.07 can be made with 3 coins instead of with 7 pennies, then later values should never consider combinations involving 7 pennies, since those could be replaced with 3 coins, decreasing the total coin count.

These observations suggest that there is a solution where our early work helps us figure out the results for later values.

Inductive definitions

In math, when we can write a definition step-wise, defining some basic objects and then defining later objects using the earlier steps, we call it an inductive or recursive definition. These objects could be sets, functions, shapes, etc. The important thing is that we start with some basic case or cases, and then continue our definition by repeatedly building on what we already have.

For example, the multiplication operation * can be defined inductively as follows:

Base cases: for each natural number n, define 0*n to be 0.
Inductive steps: for each natural number m and n, define (m+1)*n to be m*n + n.

In this definition, we would say that we are inducting on the left number, since that’s the input that we change to build up the definition.

This definition determines a value for every pair m and n because it can be used repeatedly to break down m*n to the base cases (and addition). We can use the inductive step to repeatedly decrease the left number by 1, until it reaches 0 and we can use the base case. For example, say we want to compute 3*4 using this definition. We’ll write out the computation and note how to get to the next line in each case.

3*4 =                // write the left number as 2+1
(2+1)*4 =            // use the inductive step
2*4 + 4 =            // write left number as 1+1
(1+1)*4 + 4 =        // use the inductive step
1*4 + 4 + 4 =        // write the left number as 0+1
(0+1)*4 + 4 + 4 =    // use the inductive step
0*4 + 4 + 4 + 4 =    // use the base case
0 + 4 + 4 + 4 =      // just add since all * are gone

Next we’ll look at how to use this idea for our coin problem.

Back to coins

So, how could we inductively define the function for our coin problem?

Induction variable

First, we should decide what we want to induct on. To help answer this, we think about solving the problem and ask ourselves what information is useful for answering later questions. In this case, there seems to be two options.

We can induct on the total $ value. That is, we try to understand the number of coins needed to make n cents using the solutions for m cents, where m < n. For example, we try to answer the problem for $0.07 using what we know about $0.01, $0.02, $0.03, $0.04, $0.05, and $0.06.
We can induct on the coins we use. This one is a bit more complicated to explain. In this case, we try to understand the number of coins needed to make n cents by using solutions that involve fewer denominations of coins. For example, if we have already solved the problem in a world where we only have pennies, nickels, and dimes, we can use that solution to find solutions in a world where we have pennies, nickels, dimes, and also quarters.

We’ll do our induction on the total $ value. We’ll comment on the other idea later.

Base case

In our example where we inductively defined multiplication, our base cases were the 0*n cases. Those were easy, clear cases where we could just immediately return the answer. Then we built up from there, defining multiplication for higher inputs by increasing the left side by 1 each step.

In this coin problem, if we want to induct on the total value, then we should start at $0.00 and work our way up, increasing the value by $0.01 each time. So, our base case is $0.00, which takes 0 coins. This will be our starting point.

Base case: $0.00 requires 0 coins.

Inductive steps

Now, we need to think about our inductive steps. How do we figure out the solution for n cents if we already know the solutions for m cents whenever m < n? For example, how do we figure out the solution for $0.07 when we already know the minimal number of coins needed for $0.00, $0.01, …, $0.06?

One way to get the solution for n knowing the solutions for each m < n is the following. Think about how we can arrive at a total of n cents with our coins. If we were adding our coins to a pile one at a time, then the last step before we got n cents would be to have a pile with some smaller number m cents, and add a single coin worth (n-m) cents.

Another way of saying that is, if we have coins with different values c, then we can arrive at n cents by adding one coin with c to a pile with value n-c. If it took at most K many coins to make a pile worth n-c cents, then it takes at most K+1 coins to make a pile worth n cents.

That gives us a few choices: for each coin value c, we consider our solutions for the total values n-c, and add 1 to each. Whatever the minimal value is, that’s our solution for n.

Notice that we only need to know the solutions for total values less than n to do this, so this approach fits our idea of an inductive definition. We start with our base case $0.00, then we can compute the solution for $0.01 using that, then the solution for $0.02 using those, then for $0.03 using those, etc.

Let’s make things easier to talk about by giving a name to our solutions. We will build our solution as an array called num_coins. That is, num_coins[n] will stand for the minimum number of coins required to make n cents. For example, if we have pennies, nickels, dimes, and quarters, then num_coins[7] should be 3, the number of coins needed to make a total value of $0.07.

We can write our inductive step now, in addition to our earlier base case.

Base case: num_coins[0] = 0.
Inductive step: num_coins[n] is the minimum of the values num_coins[n-c] obtained by using the different coin values c.

Some warnings

Of course, num_coins[n-c] only makes sense when c < n, both because of the way array indices work, and since we don’t want to consider how many coins it takes to make negative values. We’ll make sure to remember that in our code.

Also, what happens if there is no way to make n cents with our coins? When we have pennies ($0.01 coins), this won’t happen. But, in more general cases we might not be able to find solutions for certain values of n. For example, if we have no pennies and start at nickels ($0.05 cent coins), then we have no solutions for $0.01, $0.02, …, $0.04. We will handle this in our code.

Code

Here’s a Python implementation of our inductive definition. We’ll explicitly handle the case where we have 1 cent, 5 cent, 10 cent, and 25 cent coins, but the code will handle more general cases. This allows it to generalize to other sets of coin denominations.

coins = [1, 5, 10, 25]

# the base case, n = 0
num_coins = [0]

# the inductive cases
for n in xrange(1,101):
    # each loop computes the solution for n cents
    # we can make use of num_coins[m] for any m < n

    # use 999 coins to handle cases with no solution
    candidates = [999]
    for c in coins:
        # ignore coins that are too large for n cents
        if c <= n:
            candidates.append(num_coins[n-c]+1)
    num_coins.append(min(candidates))

print num_coins

In this case, the candidates = [999] case is irrelevant, since there will always be a solution with pennies taking at most n coins. We’ve chosen to use 999 as a default because it is larger than any solution when one exists, so the min() function will not select it.

However, if we want to generalize to other sets of coin denominations, we will need that default value. For example, removing the penny (the value 1 from the coins list) will result in many values of num_coins taking on the value 999.

Below, we have another implementation which populates the list num_coins in advance and uses repeated min() calls, rather than repeatedly creating a list of candidates to select the minimum value from.

coins = [1,5,10,25]
num_coins = [0]+[999]*100
for n in xrange(1,101):
    for c in coins:
        if c <= n:
            num_coins[n] = min(num_coins[n-c]+1, num_coins[n])

print num_coins

Dynamic programming

In the context of solving a problem, the inductive constructions are examples of dynamic programming. Roughly, dynamic programming is an approach where the problem is recursively decomposed into smaller subproblems from which the overall solution is built.

In our problem above, we solved the overall problem (finding a solution for all values up to $1.00) by viewing it as a problem for each value of n cents. We solved the problem for n cents recursively by using a base case and the solutions for m < n cents.