Bioinformatics AlgorithmsAn Active Learning Approach
You are reading the free online edition. Autograded code challenges and a certificate are in the interactive text, free to start.Solve these problems with autograders, free

Lesson 5.5

An Introduction to Dynamic Programming: The Change Problem

7 min read1 code challenge✓ Read

Watch the lectureThe Change Problem

Changing money greedily

Imagine that you bought this textbook in a bookstore for $99.24, which you paid for with $100 in cash. You are due 76 cents in change, and the cashier now must make a decision whether to give you a fistful of 76 1-cent coins or just four coins (25 + 25 + 25 + 1 = 76). Making change in this example is easy, but it casts light on a more general problem — how can a cashier make change using the fewest number of coins?

Different currencies have different possible coin values, or denominations. In the US, the coin denominations are (100, 50, 25, 10, 5, 1); in the Roman Republic, they were (120, 40, 30, 24, 20, 10, 5, 4, 1). The heuristic used by cashiers all over the world to make change, which we call GreedyChange, iteratively selects the largest coin denomination possible.

GreedyChange(money)
  change ← empty collection of coins
  while money > 0
    coin ← largest denomination that is less than or equal to money
    add a coin with denomination coin to the collection of coins change
    money ← money − coin
  return change

STOP and Think Does GreedyChange always return the minimum possible number of coins?

Say we want to change 48 units of currency (called denarii) in ancient Rome. GreedyChange returns five coins (48 = 40 + 5 + 1 + 1 + 1), and yet we can make change using only two coins (48 = 24 + 24). Thus, GreedyChange is suboptimal for some denominations!

STOP and Think During the reign of Augustus, Roman coin denominations were changed to (1600, 800, 400, 200, 100, 50, 25, 2, 1). Why did these denominations make Roman cashiers' lives easier? More generally, what do you think might dictate when GreedyChange will make change with the fewest number of coins?

Since GreedyChange is incorrect, we need to come up with a different approach. We can represent coins from d arbitrary denominations by an array of integers

Coins = (coin1, ... , coind)

where the values coini are given in decreasing order. We say that an array of d positive integers (change1, ..., changed) with the number of coins change1 + ⋯ + changed changes an integer money (for the denominations Coins) if

coin1 · change1 + ⋯ + coind · changed = money

For example, for the Roman denominations Coins = (120, 40, 30, 24, 20, 10, 5, 4, 1), both (0, 1, 0, 0, 0, 0, 0, 1, 0, 3) and (0, 0, 0, 2, 0, 0, 0, 0, 0) change money = 48.

We will consider the problem of finding the minimum number of coins needed to make change, instead of actually producing these coins. Let MinNumCoins(money) denote the minimum number of coins needed to change money for a given collection of denominations (e.g., for the Roman denominations, MinNumCoins(48) = 2).

Change Problem: Find the minimum number of coins needed to make change.

  • Input: An integer money and an array Coins of d positive integers.
  • Output: The minimum number of coins with denominations Coins that changes money.

Changing money recursively

Since the greedy solution used by Roman cashiers to solve the Change Problem is incorrect, we will consider a different approach. Suppose you need to change 76 denarii, and you only have coins of the three smallest denominations: Coins = (5, 4, 1). A minimal collection of coins totaling 76 denarii must be one of the following:

  • a minimal collection of coins totaling 75 denarii, plus one 1-denarius coin;
  • a minimal collection of coins totaling 72 denarii, plus one 4-denarius coin;
  • a minimal collection of coins totaling 71 denarii, plus one 5-denarius coin.

For the general denominations Coins = (coin1, ... , coind), MinNumCoins(money) is equal to the minimum of d numbers:

Min num coins recurrence relation

We have just produced a recurrence relation, or an equation for MinNumCoins(money) in terms of MinNumCoins(m) for smaller values m.

The recurrence relation from the preceding step motivates the following recursive algorithm (i.e., an algorithm that can call itself), which solves the Change Problem by computing MinNumCoins(m) for smaller and smaller values of m. In this algorithm, |Coins| refers to the number of denominations in Coins. See "DETOUR: The Towers of Hanoi" in the print companion or at Cogniterra if you have not yet encountered recursive algorithms.

RecursiveChange(money, Coins)
  if money = 0
    return 0
  MinNumCoins ← ∞
  for i ← 0 to |Coins| - 1
    if money ≥ coini
      NumCoins ← RecursiveChange(money − coini, Coins)
      if NumCoins + 1 < MinNumCoins
        MinNumCoins ← NumCoins + 1
  return MinNumCoins

STOP and Think Implement RecursiveChange and run it on money = 76 with Coins = (5, 4, 1). What happens?

RecursiveChange may appear efficient, but it is completely impractical because it recalculates the optimal coin combination for a given value of money over and over again. For example, when money = 76 and Coins = (5, 4, 1), MinNumCoins(70) gets computed six times, five of which are shown in the figure below. This may not seem like a problem, but MinNumCoins(30) will be computed billions of times!

Min num coins recursive tree

Figure: A tree illustrating the computation of MinNumCoins(76) for the denominations coins = (5, 4, 1). The edges of this tree represent recursive calls of RecursiveChange for different input values, with five of the six computations of MinNumCoins(70) highlighted in red. When MinNumCoins(70) is computed for the sixth time (corresponding to the path 76 → 75 → 74 → 73 → 72 → 71 → 70), RecursiveChange has already been called hundreds of times.

Changing money using dynamic programming

To avoid the many recursive calls that are needed to compute MinNumCoins(money), we will use a dynamic programming strategy. Wouldn’t it be nice to know all the values of MinNumCoins(money − coini) by the time we compute MinNumCoins(money)? Instead of the time-consuming calls to RecursiveChange(money − coini, Coins), we could simply look up the values of MinNumCoins(money − coini) in an array and thus compute MinNumCoins(money) using just |Coins| comparisons.

The key to dynamic programming is to take a step that may seem counterintuitive. Instead of computing MinNumCoins(m) for every value of m from 76 downward toward m = 0 via recursive calls, we will invert our thinking and compute MinNumCoins(m) from m = 0 upward toward 76, storing all these values in an array so that we only need to compute MinNumCoins(m) once for each value of m. MinNumCoins(m) is still computed via the same recurrence relation:

Min num coins recurrence relation example

For example, assuming that we have already computed MinNumCoins(m) for m < 7, MinNumCoins(6) is equal to one more than the minimum of MinNumCoins(6 - 5) = 1, MinNumCoins(6 - 4) = 2, and MinNumCoins(6 - 1) = 1. Thus, MinNumCoins(6) is equal to 1 + 1 = 2. In turn, MinNumCoins(7) is equal to one more than the minimum of MinNumCoins(7 - 5) = 2, MinNumCoins(7 - 4) = 3, and MinNumCoins(7 - 1) = 2. As a result, MinNumCoins(7) is equal to 2 + 1 = 3. And so on, resulting in the following table.

Min num coins table

Figure: MinNumCoins(m) for values of m between 0 and 12.

Exercise Break Use dynamic programming to fill in the next ten values of MinNumCoins(m) (i.e., for 13 ≤ m ≤ 22). Place all the values on a single line. Solve at Cogniterra.

Min num coins table

Notice that MinNumCoins(2) is used in the computation of both MinNumCoins(6) and MinNumCoins(7), but instead of draining computational resources by having to compute this value from scratch both times, we simply consult the pre-computed value in the array. The following dynamic programming algorithm calculates MinNumCoins(money) with runtime O(money · |Coins|).

DPChange(money, Coins)
  MinNumCoins(0) ← 0
  for m ← 1 to money
    MinNumCoins(m) ← ∞
      for i ← 0 to |Coins| - 1
        if m ≥ coini
          if MinNumCoins(m - coini) + 1 < MinNumCoins(m)
            MinNumCoins(m) ← MinNumCoins(m - coini) + 1
  output MinNumCoins(money)
Try it Making change three ways: greedy, recursive, and dynamic programming

Ready to write it yourself? Implement DPChange in the interactive text.

Code Challenge Solve the Change Problem. The DPChange pseudocode is reproduced below for your convenience. Solve at Cogniterra or Rosalind.Solve it with the autograderFree to start in the interactive text

  • Input: An integer money and an array Coins = (coin1, ..., coind).
  • Output: The minimum number of coins with denominations Coins that changes money.
DPChange(money, Coins)
  MinNumCoins(0) ← 0
  for m ← 1 to money
    MinNumCoins(m) ← ∞
      for i ← 0 to |Coins| - 1
        if m ≥ coini
          if MinNumCoins(m - coini) + 1 < MinNumCoins(m)
            MinNumCoins(m) ← MinNumCoins(m - coini) + 1
  output MinNumCoins(money)

STOP and Think Consider the following modifications of DPChange.

  1. If money = 109, DPChange requires a huge array of size 109. Modify the DPChange algorithm so that the array size required does not exceed the value of the largest coin denomination.
  2. Recall that our original goal was to make change, not just compute MinNumCoins(money). Modify DPChange so that it not only computes the minimum number of coins but also returns these coins.