How many ways can you make change for a dollar?

You could use 100 pennies. You could use two half-dollars. You could use three quarters, two dimes, and one nickel. You could use one quarter, two dimes, four nickels, and 35 pennies.

And so on and so forth. It’s easy to see that there are a lot of ways to make change for a dollar. But, for any given amount of money, there is a conceptually simple — and clever — way to compute the number of ways that you can make change for it.

Let’s say that there is a list of coin denominations, and you can choose from each denomination as many coins as you need. So, in this case, we have two half-dollars, four quarters, ten dimes, 20 nickels, and 100 pennies. Those are all the coins that you need.

For any given amount of money, the number of ways to make change for it is just the number of ways to make change for it using the first denomination on the list, plus the number of ways to make change for it without using the first denomination on the list.

We are applying a divide-and-conquer strategy. You divide the problem into subproblems until you get problems that are trivially solvable. Then, to produce a solution to the original problem, you combine all of the solutions to the subproblems.

So, for example, our problem is to compute the number of ways to make change for a given amount of money. We divide that problem into two subproblems:

(1) Compute the number of ways to make change for the amount of money using the first denomination in our list of denominations

(2) Compute the number of ways to make change for the amount of money without using the first denomination in our list

If it’s trivial to solve a subproblem, then solve it. If it’s not trivial to solve, then divide it into two subproblems of its own.

Two parameters define the coin change problem: (1) the amount of money that you must make change for and (2) the list of coin denominations. So, you can reduce the size of a problem instance in two ways: (1) You can decrease the amount of money that you must make change for, and (2) you can shorten the list of coin denominations.

Option (1) corresponds to subproblem (1). When you use the first denomination in the list, you decrease the amount of money that you must make change for. So, for example, let’s say that you must make change for one dollar and you decide to use a half-dollar, the first denomination in your list of denominations. Now that you’ve put in a half-dollar, you just have to make change for 50 cents. So, you’ve decreased the amount of money that you must make change for.

Option (2) corresponds to subproblem (2). If you don’t use the first denomination in your list of denominations, then you effectively shorten your list of denominations. For example, let’s say that your list of denominations is {half-dollars, quarters, dimes, nickels, pennies}. If you decide not to use half-dollars, then your list of denominations effectively becomes {quarters, dimes, nickels, pennies}.

You continually reduce the size of your problem until you finally reach instances of the problem that are trivially solvable. These are the trivial instances of the coin change problem:

-You must make change for no amount of money. There is one way to solve that problem: You use no coins.

-You must make change for a negative amount of money. There is no way to do that.

-You must make change for some amount of money, but there are no denominations to choose coins from. In this case, too, there are zero ways to make change.

You solve these problems and then combine them to create a solution to the original problem. In this case, you combine them through addition. The number of ways to make change for some amount of money is the number of ways to make change for it using the first denomination on the list, **plus** the number of ways to make change for it without using the first denomination on the list.

The subproblems are the same type of problem that the original problem is, because the subproblems require you to compute the number of ways to make change for a given amount of money, too. So, we apply the same problem-solving procedure to the subproblems that we do to the original problem. Consequently, it is natural to deploy a recursive algorithm, as it was when I implemented a solution to the Towers of Hanoi problem.

I decided to employ recursion, and I implemented the algorithm in Scheme.

Notice that this is a top-down approach to solving problems. You start with a problem and divide it into smaller and smaller pieces, working your way down until you arrive at pieces that are trivially solvable.

But you don’t have to approach our problem in a top-down way. Instead you can employ a bottom-up approach, where you start with the solutions to the smallest subinstances of the problem and continually build on them until you get up to a solution to the whole problem.

Because the top-down, recursive approach typically has to process a lot of the same subinstances and the bottom-up approach does not, the bottom-up approach is typically a lot faster. For example, in this case, the bottom-up approach is O(D * M), where D is the number of coin denominations and M is the amount of money (in cents). In contrast, if you don’t memoize the recursive solution, it runs in exponential time.

As I have in the past, I used dynamic programming to design just such a bottom-up strategy. (That program also features a naive recursive solution and a memoized recursive solution.)

To find the maximum independent set of any tree, I also designed a bottom-up, dynamic-programming algorithm and implemented a top-down, recursive algorithm.

The approaches to the maximum independent set problem feature a technique that the approaches to the coin change problem also feature: The use of inclusion and non-inclusion to neatly divide the problem into just two subproblems. So, the maximum independent set of a tree either includes the root of the tree or it doesn’t include the root of the tree. Exploiting that fact, you construct the independent set that includes the root and the independent set that doesn’t include the root, and then you take the larger of the two. Likewise, to count the total number of ways that you can make change for some amount of money, you count the number of ways that you can make change for it if you include the first denomination on the list and the number of ways that you can make change for it if you do not include the first denomination on the list.

I have found that many dynamic programming approaches feature this technique. For example, an approach to the discrete knapsack problem features it, too: To compute the maximum value that the knapsack can contain, you compute the value when you include the current item and when you don’t include the current item, and then you take the larger of the two.

MIT professor Erik Demaine has said that an essential part of dynamic programming is guessing. In his opinion, dynamic programming is “careful brute force”. If you don’t know the solution to some problem, then try every possible solution and take a best one. And that is what is going on in these procedures that solve the discrete knapsack problem, the maximum independent set problem, and the coin change problem. The technique that all of these procedures deploy is just a clever way to partition the set of all possible solutions. So, any solution to the coin change problem either includes the first denomination in the list of denominations or it doesn’t include it, and these are the only two possibilities. So, to find the total number of ways to make change for a given amount of money, we just have to process both of these possibilities and combine the results.