Rebuilding the answer

A DP table holds values: the LCS length, the best total. Usually you also want the thing itself: the letters, the items, the route. This lesson shows how to get it by walking back through the table, how to store choices when walking back is hard, and what to do when memory is short.

A number is not a choice

Every cell’s value came from one of a few cells, through one of a few choices: take or skip, match or drop. The table does not record which. But the rule can be checked again: if a cell’s value equals what one choice would give, that choice is a valid way to reach it. Starting from the answer cell and repeating this check leads back to a base case, and the choices met on the way make up an answer.

Walking back

For the LCS (lesson 7): at cell (i, j), if the last letters are equal, the letter is in the LCS; collect it and move diagonally. Otherwise move to whichever of the cell above and the cell to the left holds the larger value; on a tie, either one is fine. The letters come out last first, so reverse them at the end. Step through the first version of the figure.

def lcs(a, b):
    n, m = len(a), len(b)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    out = []
    i, j = n, m
    while i > 0 and j > 0:              # walk back
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif L[i - 1][j] >= L[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))

Each step moves up, left or both, so the walk takes at most n + m steps: nothing next to the O(n · m) table. The walk needs the whole table, so the two-row version of lesson 7 is not enough here.

Which items?

For the knapsack (lesson 8), keep every row. At row i with x kilograms left, compare best[i][x] with the cell above, best[i - 1][x]. If they are equal, the best value is possible without item i: skip it and move up. If not, item i must have been taken: collect it, and move up to x − wᵢ kilograms. The second version of the figure walks back from 9 and finds B and C.

The same check works for any table: compare the cell with what each choice would give. Writing the knapsack walk is DYNP-P9.

Storing the choice

Sometimes checking the rule again is slow or awkward. Then store the choice as the table is filled: a second table, or for 1-D problems a list prev, where prev[i] says which state the best answer at i came from. Walking back is then following prev until it runs out.

The O(n log n) increasing subsequence (lesson 6) needs this, because tails is not itself a subsequence. Keep the position of each tail, and for each value the position of the value before it:

from bisect import bisect_left

def lis(a):
    tail_val, tail_pos = [], []  # tails, and where they are
    prev = [-1] * len(a)          # the value before, in its run
    for i, x in enumerate(a):
        k = bisect_left(tail_val, x)
        if k > 0:
            prev[i] = tail_pos[k - 1]
        if k == len(tail_val):
            tail_val.append(x)
            tail_pos.append(i)
        else:
            tail_val[k] = x
            tail_pos[k] = i
    out = []
    i = tail_pos[-1] if a else -1
    while i != -1:
        out.append(a[i])
        i = prev[i]
    return out[::-1]

When x arrives and bisect_left returns k, it extends a subsequence of length k that ends at tail_pos[k - 1], so that is its prev. Later changes to tails do not change prev[i], so each chain stays valid. The extra cost is one list of n positions.

Rebuilding with little memory

Keeping the whole table costs O(n · m) memory: 100 million numbers for two strings of 10,000 letters, too much for Python lists. There are three ways out.

• Store one bit per cell for the choice, instead of a number. That is about 8 times smaller than a table of 8-byte numbers, and much smaller than a table of Python objects. A bytearray or a whole number used as bits (BITS) holds them.
• Divide and conquer (Hirschberg’s method, 1975). Fill the length table for the top half of a’s letters forwards, and for the bottom half backwards (on the reversed strings), keeping one row each. Where the two middle rows add up to the LCS length, the LCS crosses the middle: split b there and solve the two halves the same way (DVCQ). The time stays O(n · m), about twice the work, and the space is O(n + m).
• Keep some rows only (checkpoints): keep every k-th row, and refill the rows between two checkpoints when the walk needs them. With k near √n (the square root of n), the memory is O(√n · m) and the time about doubles.

Now try DYNP-P9, Which items to pack. This is the last lesson of the station; advanced DP (on trees, on intervals, over subsets) comes in ADDP, after the graph stations.