Unit 7: Remember the Answer

The three questions

Every dynamic programming solution answers the same three questions.

What is the state? The smallest description of a part-finished problem. What are the moves? How a state is reached from smaller ones. Where does it start? The state whose answer needs no working out.

Get those three right and the code writes itself.

Back to the coins that beat greedy

Unit 4 paid 8 pence with coins of 1, 4 and 5, and greedy used four coins when two would do. Here is the fix.

State: an amount. Moves: pay one coin, leaving a smaller amount. Start: 0 pence needs 0 coins.

Python

coins = [1, 4, 5]
target = 8
big = 999

best = [0] + [big] * target
for amount in range(1, target + 1):
    for c in coins:
        if c <= amount:
            best[amount] = min(best[amount], best[amount - c] + 1)

print(best)
print(best[target])

It prints

[0, 1, 2, 3, 1, 1, 2, 3, 2]
2

Every amount is worked out once, and never again

That is the whole idea. The plain recursion from unit 4 asks "how do I pay 4 pence?" over and over; the table asks once and writes it down.

The cost is the number of states times the number of moves: amount * coins. A million pence and ten coins is ten million steps, which fits in a second.

The same thing, upside down

Filling a table from the bottom is one way. The other is the recursion you already had, plus a notebook of answers already found — memoisation.

Identical work, and the notebook shows it: eight amounts were ever asked about.

Python

coins = [1, 4, 5]
memo = {}

def fewest(amount):
    if amount == 0:
        return 0
    if amount in memo:
        return memo[amount]
    best = 999
    for c in coins:
        if c <= amount:
            best = min(best, fewest(amount - c) + 1)
    memo[amount] = best
    return best

print(fewest(8), len(memo))

It prints

2 8

Swap the min for a plus

"How few coins?" becomes "how many ways?" by changing one operator. Instead of keeping the best move, add up what every move offers.

The start changes too: there is exactly one way to pay nothing.

Python

coins = [1, 3, 4]
target = 5

ways = [1] + [0] * target
for c in coins:
    for amount in range(c, target + 1):
        ways[amount] += ways[amount - c]

print(ways)

It prints

[1, 1, 1, 2, 3, 3]

Now swap the two loops round

Same numbers, same +=, loops the other way about — and the answer is 6 instead of 3.

Neither is a bug. With the coins outside, 1+4 and 4+1 are the same handful of coins. With the amounts outside, they are two different ways to pay.

Python

coins = [1, 3, 4]
target = 5

ways = [1] + [0] * target
for amount in range(1, target + 1):
    for c in coins:
        if c <= amount:
            ways[amount] += ways[amount - c]

print(ways)

It prints

[1, 1, 1, 2, 4, 6]

Read the question, then choose the loop

If the problem says "in how many ways can you pay" and the coins are a handful, you want the first one. If it says "how many sequences of steps", you want the second.

Getting this backwards is one of the most common wrong answers in contest history, and it costs nothing to check: try it on 5 with coins 1, 3 and 4 and see whether you expected 3 or 6.

The same shape on a grid

Paths from the top left to the bottom right, moving only right or down. The ways into a square are the ways into the square above plus the ways into the square to its left — and a wall has no ways at all.

Python

grid = [
    "....",
    ".#..",
    "....",
]

rows = 3
cols = 4
ways = [[0] * cols for r in range(rows)]
ways[0][0] = 1

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == "#":
            ways[r][c] = 0
            continue
        if r > 0:
            ways[r][c] += ways[r - 1][c]
        if c > 0:
            ways[r][c] += ways[r][c - 1]

for row in ways:
    print(row)

It prints

[1, 1, 1, 1]
[1, 0, 1, 2]
[1, 1, 2, 4]

Pick numbers going up, without reordering them

From 7, 3, 5, 3, 6, 2, 9 pick as many as you can, in the order they appear, each bigger than the last. The best is 3, 5, 6, 9 — four of them.

This is the longest increasing subsequence, and it turns up in contests constantly, usually in disguise.

The state is "climbs ending here"

length[i] is the longest climb that finishes at position i. To fill it, look back at every earlier position holding a smaller number and take the best of those, plus one.

Two loops, so O(n * n): fine to 5000 numbers, and the answer is the biggest entry rather than the last one.

Python

numbers = [7, 3, 5, 3, 6, 2, 9]
n = len(numbers)

length = [1] * n
for i in range(n):
    for j in range(i):
        if numbers[j] < numbers[i]:
            length[i] = max(length[i], length[j] + 1)

print(length)
print(max(length))

It prints

[1, 1, 2, 1, 3, 1, 4]
4

A million numbers needs something better

Keep a list of ends: tails[k] is the smallest number that any climb of length k + 1 can end on. Small ends are worth more, because more numbers can follow them.

For each new number, find where it belongs with a binary search. Off the end — it extends the longest climb. Inside — it becomes a better end for that length.

Python

import bisect

numbers = [7, 3, 5, 3, 6, 2, 9]
tails = []
for x in numbers:
    pos = bisect.bisect_left(tails, x)
    if pos == len(tails):
        tails.append(x)
    else:
        tails[pos] = x
    print(x, tails)

print(len(tails))

It prints

7 [7]
3 [3]
5 [3, 5]
3 [3, 5]
6 [3, 5, 6]
2 [2, 5, 6]
9 [2, 5, 6, 9]
4

Careful: that list is not the answer

tails ends up as [2, 5, 6, 9], and that is not a climb in the original list — the 2 comes after the 6.

Only its length is right. If a problem asks for the climb itself you have to record where each number came from, which is the usual reason people lose marks on this one.

A bag that holds 6 kilos

Three things to take: 3kg worth 4, 4kg worth 5, 2kg worth 3. The bag holds 6 kilos, and each thing can be taken once or not at all.

Greedy by value picks the 5 and then the 3 — 6 kilos, worth 8. Here greedy happens to be right, and on the next data it will not be.

One row per item

best[c] is the most value that fits in c kilos using the items seen so far. Take each item in turn and let it improve every capacity it fits in.

Watch the row change as each item is offered.

Python

items = [(3, 4), (4, 5), (2, 3)]
capacity = 6

best = [0] * (capacity + 1)
for weight, value in items:
    for c in range(capacity, weight - 1, -1):
        best[c] = max(best[c], best[c - weight] + value)
    print(best)

print(best[capacity])

It prints

[0, 0, 0, 4, 4, 4, 4]
[0, 0, 0, 4, 5, 5, 5]
[0, 0, 3, 4, 5, 7, 8]
8

The capacity loop runs backwards for a reason

Forwards, best[c - weight] may already include this item, so it gets taken twice. Backwards, the value it reads is always from before this item existed.

Here is the same item offered forwards: one 3kg item worth 4 somehow fills a 6kg bag with 8.

Python

capacity = 6
weight = 3
value = 4

best = [0] * (capacity + 1)
for c in range(weight, capacity + 1):
    best[c] = max(best[c], best[c - weight] + value)

print(best)

It prints

[0, 0, 0, 4, 4, 4, 8]

So the direction is the difference between two problems

Backwards is the 0/1 knapsack — each item once. Forwards is the unbounded knapsack — as many of each as you like, which is exactly what the coin problems in lessons 1 and 2 were.

One word in the problem statement decides it, and one word in your loop answers it.

Unit 2 tried every order. Now count what that cost

Twenty towns, every order: about two million million million tours. There is no computer on earth that finishes that.

But think about what actually matters half way round a tour: which towns you have already visited, and where you are standing. Not the order you did them in.

Python

import math

for n in [10, 15, 20]:
    print(n, math.factorial(n - 1), (1 << n) * n * n)

It prints

10 362880 102400
15 87178291200 7372800
20 121645100408832000 419430400

The state is a bitmask and a town

So the state is (visited, here) — and unit 3 already showed that a set of visited towns is just a number.

There are 2 n masks times n towns of them, and from each you may move to any of n towns. That is the 2 n * n * n in the table, and for 20 towns it is 400 million: big, but finite.

Filling it in

Start in town 0 with only town 0 visited, at cost 0. From every reachable state, step to a town that is not in the mask yet and write down the cheaper of what is there and what you have.

At the end, every town has been visited: add the road home and take the best.

Python

d = [
    [0, 5, 9, 4],
    [5, 0, 3, 8],
    [9, 3, 0, 6],
    [4, 8, 6, 0],
]
n = 4
big = 10 ** 9

dp = [[big] * n for mask in range(1 << n)]
dp[1][0] = 0

for mask in range(1 << n):
    for here in range(n):
        if dp[mask][here] == big:
            continue
        for nxt in range(n):
            if (mask >> nxt) & 1:
                continue
            step = dp[mask][here] + d[here][nxt]
            if step < dp[mask | (1 << nxt)][nxt]:
                dp[mask | (1 << nxt)][nxt] = step

full = (1 << n) - 1
print(min(dp[full][i] + d[i][0] for i in range(1, n)))

It prints

18

The same 18 as unit 2, and that is the point

Complete search got 18 by looking at six whole tours. This gets 18 by filling in 64 little boxes, and it would still be working at twenty towns where complete search stopped being possible.

Nothing was approximated. The answer is exactly the same one — found by asking a better question about what a half-finished tour needs to remember.