Introduction to Dynamic Programming

You are building the change dispenser for a ticket machine. It has coins worth 1, 4 and 5, as many of each as it needs. A customer is owed 8. The machine should hand over as few coins as possible.

The obvious rule is "always take the biggest coin that fits". That gives 5, then 1, 1, 1: four coins. But 4 + 4 is only two coins. Taking the biggest coin first looked safe and was wrong, the same trap you saw in Greedy Algorithms. To get the right answer you have to consider every first coin. That is where this lesson starts.

#Version 1: honest, slow recursion

Think about the first coin the machine hands over. It is a 1, a 4 or a 5. Whichever it is, what remains is the same problem with a smaller amount. If you owe 8 and hand over a 4, you now owe 4.

So the fewest coins for 8 is one coin plus the best of three smaller answers: the fewest coins for 7, for 4, or for 3. Each of those breaks down the same way, until you reach 0, which needs no coins at all.

// Fewest coins that add up to amount (Infinity if impossible).
function fewestCoins(amount, coins) {
  if (amount === 0) return 0;
  let best = Infinity;
  for (const coin of coins) {
    if (coin <= amount) {
      best = Math.min(best, 1 + fewestCoins(amount - coin, coins));
    }
  }
  return best;
}
 
fewestCoins(8, [1, 4, 5]); // 2

import math
 
# Fewest coins that add up to amount (math.inf if impossible).
def fewest_coins(amount, coins):
    if amount == 0:
        return 0
    best = math.inf
    for coin in coins:
        if coin <= amount:
            best = min(best, 1 + fewest_coins(amount - coin, coins))
    return best
 
fewest_coins(8, [1, 4, 5])  # 2

This is correct. For 8 it makes 35 calls. For 30 it makes 255,904 calls. There are only 31 different amounts between 0 and 30, so almost all of that work is repeated.

You saw the same waste with Fibonacci in Recursion. Two things are true here, and together they are the signal for dynamic programming:

• The big answer is built from smaller answers. The best way to pay 8 is one coin plus the best way to pay what is left.
• The smaller problems repeat. Different paths through the recursion keep landing on the same amount.

#Version 2: remember answers (memoisation)

The fix is small. Keep a map from amount to answer. Before working anything out, check the map. After working it out, store it. Each amount is now solved once; every later visit is a single lookup.

function fewestCoinsMemo(amount, coins, memo = new Map()) {
  if (amount === 0) return 0;
  if (memo.has(amount)) return memo.get(amount); // solved before
  let best = Infinity;
  for (const coin of coins) {
    if (coin <= amount) {
      best = Math.min(best, 1 + fewestCoinsMemo(amount - coin, coins, memo));
    }
  }
  memo.set(amount, best); // remember for next time
  return best;
}

def fewest_coins_memo(amount, coins, memo=None):
    if memo is None:
        memo = {}
    if amount == 0:
        return 0
    if amount in memo:  # solved before
        return memo[amount]
    best = math.inf
    for coin in coins:
        if coin <= amount:
            best = min(best, 1 + fewest_coins_memo(amount - coin, coins, memo))
    memo[amount] = best  # remember for next time
    return best

For 30, the call count drops from 255,904 to 84. The logic did not change at all. You only stopped throwing answers away.

#Version 3: fill a table from the bottom

Memoisation still works top-down, from 8 toward 0. But every amount only depends on smaller amounts. So you can skip the recursion and work upward: solve 0, then 1, then 2, and so on. By the time you reach any amount, everything it needs is already in the table. This is called tabulation.

best = [∞] * (amount + 1)best[0] = 0for a from 1 to amount:  for coin in coins:    if coin <= a:      best[a] = min(best[a], 1 + best[a - coin])return best[amount]

function fewestCoinsTable(amount, coins) {
  const best = new Array(amount + 1).fill(Infinity);
  best[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) best[a] = Math.min(best[a], 1 + best[a - coin]);
    }
  }
  return best[amount]; // Infinity means "cannot be paid"
}
 
fewestCoinsTable(8, [1, 4, 5]); // 2

def fewest_coins_table(amount, coins):
    best = [math.inf] * (amount + 1)
    best[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                best[a] = min(best[a], 1 + best[a - coin])
    return best[amount]  # math.inf means "cannot be paid"
 
fewest_coins_table(8, [1, 4, 5])  # 2

Memoisation and tabulation do the same work. Memoisation is often easier to write first, because it is your recursion plus three lines. Tabulation has no recursion, so it cannot overflow the call stack on a large amount, and it is usually a little faster.

#The five-step recipe

Every dynamic programming solution in this module is written the same way. Get these five answers down in words before you write any code:

1. State. What does one cell of the table mean? Here: best[a] is the fewest coins that add up to exactly a.
2. Recurrence. How is a cell built from smaller cells? Here: best[a] = 1 + min(best[a − coin]) over every coin that fits.
3. Base cases. Which cells do you know without asking anything? Here: best[0] = 0.
4. Order. Which way do you fill the table so each cell's inputs are ready? Here: from 0 upward.
5. Answer. Which cell holds the result? Here: best[amount].

Step 1 is where the thinking happens. If you cannot say in one sentence what a cell means, the recurrence will not come. The other four steps usually follow from it.

The rule of thumb for any DP: time = number of cells × work per cell. Here there are A + 1 cells and each one tries k coins.

#Common mistakes

#Check yourself

#What to practise next

The coin table was one row of cells, each looking back at a few earlier cells. That shape covers a whole family of problems, from choosing work shifts to counting ways up a staircase, and it is the subject of 1D Dynamic Programming. Use the five steps there on purpose, even when the answer looks obvious. To practise the coin table itself, try Cookie Box Order.