Reconstructing the answer by storing choices in Python

Why it matters

A dynamic programming table gives a number. The longest common subsequence program can say the answer has length 4. The edit distance program can say two words are 3 edits apart. A route planner that finds the cheapest route needs the route, not only its cost. A diff tool needs the lines that were kept, not only a count of the changes.

The method in this lesson gets the path as well as the number. While the table is being filled, write down one small fact for each cell: which neighbour gave the value. After the table is full, start at the last cell and follow those notes backwards, one cell at a time, until you reach the start. The notes are called choices. Each step of the walk back costs one lookup, so the walk is fast.

You should know the DP recipe, and you should have read the longest common subsequence lesson earlier in this module, because the first example below uses the same table. You should also know one Python feature that this lesson uses: the enum. An enum is a fixed list of named values, such as Move.MATCH, Move.UP or Move.LEFT. Python provides enums in the enum module. A match statement, added in Python 3.10, runs the block that fits one value. Each case line names a value, and the first case that fits runs. If you know Java, match plays the role of the arrow form of switch.

The programs in this lesson were run with Python 3.14.4. Each one is a complete file. Save it as main.py and run it with python3 main.py.

A number does not show the path

Suppose the table is full. The cell in the last row and last column holds 4 for AGGTAB and GXTXAYB. That number does not say which four letters make the answer, or which cells the walk should visit.

You could work backwards without any notes. At each cell, check whether the last letters match. If they do not match, check which neighbour has the bigger value. This works, but it repeats the same comparisons. It also has to use the same tie rule the forward pass used. If the two passes disagree on a tie, the walk gives a path that does not match the number.

Storing the choice avoids both problems. The forward pass decides the choice once, when it computes the cell, and the walk back only reads it. The cost is one extra table of the same size as the value table.

Example 1: the letters of a longest common subsequence

The strings are a = "AGGTAB" and b = "GXTXAYB". The longest common subsequence is GTAB, with length 4.

Each cell gets one of four choices.

• MATCH: the last letters are equal. The value is the diagonal cell plus 1, and the walk back adds that letter and moves diagonally.
• UP: the last letters differ, and the cell above is at least as large as the cell to the left. The value is copied from above, and the walk back moves up.
• LEFT: the last letters differ, and the cell to the left is larger. The value is copied from the left, and the walk back moves left.
• NONE: the cell is on the top row or the left column, which stand for empty prefixes. These cells have no choice, because the walk stops before it reaches them.

The program below fills the value table and the choice table together, then walks back from the last cell.

The output is:

LCS length = 4
LCS = GTAB

The walk collects letters from the end of the string first, so the program reverses the list at the end. reversed(letters) gives the items in the opposite order, and "".join(...) glues the letters into one string with nothing between them. The _ in case _: matches any value, so it is the default branch.

The enum values are written Move.MATCH in each case line. The reason is in the mistakes section.

Watching the walk

To see each step, add one line before the match statement in the walk. The line prints the cell and the choice stored there. The .name part gives the name of an enum value as text.

print(f"at ({i},{j}) move {choice[i][j].name}")

The output of the program with that line added is:

LCS length = 4
at (6,7) move MATCH
at (5,6) move LEFT
at (5,5) move MATCH
at (4,4) move LEFT
at (4,3) move MATCH
at (3,2) move UP
at (2,2) move LEFT
at (2,1) move MATCH
LCS = GTAB

Read the first two lines. At cell (6,7), the last letters are B and B, so the choice is MATCH. The walk adds B and moves to (5,6). At (5,6), the letter A from a and the letter Y from b differ. The stored choice is LEFT, so the walk moves to (5,5) without adding anything. The walk adds four letters in total, B, A, T and G, which read backwards as GTAB.

Notice that the walk never checks letters on a mismatch. It only follows the stored choice. The choice table does that work.

Example 2: the steps of an edit

The edit distance problem asks for the fewest changes that turn one word into another. A change is an insert, a delete or a replace. The value table tells you the number of changes. The choice table tells you which change happened at each cell.

Here is the meaning of each cell, dp[i][j]. It is the fewest changes that turn the first i letters of a into the first j letters of b.

• The top row is i = 0. Turning nothing into j letters takes j inserts. Each cell there, except the corner, has the choice INSERT.
• The left column is j = 0. Turning i letters into nothing takes i deletes. Each cell there has the choice DELETE.
• If the last letters match, nothing changes at that position. The value is the diagonal cell, and the choice is MATCH.
• Otherwise the value is the smallest of three options: replace (the diagonal cell plus 1), delete (the cell above plus 1) or insert (the cell to the left plus 1). The choice is the option that gave the smallest number. The choice checks replace first, then delete, then insert, so if two options tie, replace wins over delete, and delete wins over insert. The tie order is a rule the program makes. Any fixed order works, as long as the same rule is used for every cell.

The walk back goes from the end of both words to the start, so each step is added to the front of a list. The program uses deque, a double-ended queue from the collections module. A deque adds and removes items at both ends quickly, and appendleft adds to the front. Adding each step to the front puts it before the steps that were found earlier, so the output reads from start to end.

The program below fills both tables, prints the distance, then walks back and prints the steps.

The output is:

distance = 3
1. replace k with s
2. keep i
3. keep t
4. keep t
5. replace e with i
6. keep n
7. insert g

The distance is 3, and the list has three steps that change something: the replace on line 1, the replace on line 5 and the insert on line 7. The keep lines are matches. Reading the list from top to bottom gives the edits in order, starting from the first letter of kitten.

The loop condition is i > 0 or j > 0, not and. Some steps only move along one side. A delete moves only i, and an insert moves only j. The loop has to keep going while either index is above 0. With and, an empty first word stops the loop at once and prints no steps.

Here is the same program with a = "" and b = "ab". The walk stays in the top row, so every step is an insert.

distance = 2
1. insert a
2. insert b

Example 3: the cells of a path through a grid

The third example is a grid of numbers. Each cell holds a cost. A walker starts at the top-left cell, moves only right or down, and stops at the bottom-right cell. The goal is the path with the smallest total cost, and the program must print the cells on that path.

The value table best[r][c] holds the smallest total cost to reach cell (r, c). The choice is simpler here, so the program uses a table of bool values. A bool is either True or False. The value True means the best way into the cell came from above. The value False means it came from the left. With only two options, a bool is a complete choice.

The output is:

minimum sum = 7
(0,0) value 1
(0,1) value 3
(0,2) value 1
(1,2) value 1
(2,2) value 1

The path goes across the top row and down the right column. Its values are 1, 3, 1, 1 and 1, which add up to 7.

The walk-back condition needs a closer look. The walker must move up when it is in the left column, because there is no cell to the left. It must move left when it is in the top row, because there is no cell above. Inside the grid, the stored choice decides. The condition r > 0 and (c == 0 or from_above[r][c]) says: move up if there is a row above and either there is no column to the left or the choice says the value came from above. Any other case moves left. Python checks r > 0 first, so the walk never reads from_above[0][c] for a cell in the top row.

The top-left cell is not in the loop, because the loop stops when both r and c are 0. The program adds that cell after the loop.

Checking the walk

A walk that prints a path should be checked against the number it was meant to explain. For the grid, the printed values are 1, 3, 1, 1 and 1. Their total is 7, which matches minimum sum. For the edit distance, the distance is 3, and the walk printed three steps that change something. If the two numbers disagreed, the choice table would be wrong, and the fix would be in the forward pass, not in the walk.

This check costs almost nothing, and it catches the most common mistake in this lesson: a choice stored in one branch and a value written in another.

Common mistakes

Using or and and in the wrong place

The LCS walk must stop when either index reaches 0, because the cells in row 0 and column 0 have the choice Move.NONE. Writing and in the loop condition means the walk stops as soon as one index reaches 0. Writing or means the walk keeps going into row 0 or column 0, where the choice is Move.NONE, and the case _: branch raises an error.

Here is the LCS program with and changed to or in the while line. Its output is:

LCS length = 4
Traceback (most recent call last):
  File "main.py", line 50, in <module>
    raise RuntimeError(f"no choice at {i}, {j}")
RuntimeError: no choice at 1, 0

The walk reached row 1, column 0. That cell is on the left edge, so it has no choice. The walk should have stopped before it.

Writing a bare name in a case line

A case line that uses a plain name, such as case MATCH:, does not compare with the enum value. A plain name in a pattern is a capture pattern. It matches any value and stores the value in a new name. Python checks this when it compiles the file, so the program does not run at all. Here is a small file with that mistake:

from enum import Enum
 
 
class Move(Enum):
    NONE = 0
    MATCH = 1
    UP = 2
    LEFT = 3
 
 
choice = Move.UP
match choice:
    case MATCH:
        print("match")
    case UP:
        print("up")
    case _:
        print("other")

Python rejects the file with this message:

  File "main.py", line 13
    case MATCH:
         ^^^^^
SyntaxError: name capture 'MATCH' makes remaining patterns unreachable

If the file had only the one case MATCH: line, it would match every value and take that branch, with no error at all. Write case Move.MATCH: with the enum name in front, so the pattern compares with the value.

Storing a choice that does not match the value

The choice must be written in the same branch that writes the value. If the value comes from the cell above but the program stores Move.LEFT, the walk moves the wrong way. The path then adds up to a different number, or it prints letters that do not match. The fix is to keep the value line and the choice line next to each other, as the programs above do.

Printing the steps in reverse order

The walk back finds the last step first. If the program used append instead of appendleft, the printed list would run from the end of the words to the start. For the edit distance example, the first printed line would be insert g instead of replace k with s. The fix is appendleft, or collecting the steps with append and calling reversed on the list before printing. A plain list with insert(0, step) also works, but every insert at the front moves all the other items, so a deque is the better tool here.

Expecting the rolling rows from the last lesson

The previous lesson kept only two rows of the value table. That trick does not work here, because the walk back needs the choice for every cell it might visit, and those can be in any row. The choice table has the same size as the value table, so memory is the same order as the full table. There is a method, called Hirschberg's algorithm, that recovers the path with less memory, but it is outside this lesson.

Practice

Exercise 1. In the grid program, change the cell in row 1, column 1 from 5 to 100. What does the program print?

Show the answer

It prints minimum sum = 7 and the same five cells as before. The middle cell was not on the best path, so the change does not affect the answer. The path through the top row and the right column still costs 7.

Exercise 2. Run the edit distance program on flaw and lawn. What are the distance and the steps?

Show the answer

The distance is 2. The steps are delete f, keep l, keep a, keep w and insert n. Two steps change something, so the distance is 2.

Exercise 3. In the LCS program, change >= to > on the line that compares the cell above with the cell to the left. Does the printed letter string change for AGGTAB and GXTXAYB?

Show the answer

It does not change. The program still prints LCS = GTAB, and the length is still 4. A different tie rule can change which letters are printed for other inputs, but the length never changes, because the value table is the same.

Exercise 4. Why does the LCS walk never read the choice of a cell in row 0 or column 0?

Show the answer

The loop is while i > 0 and j > 0. It stops as soon as either index reaches 0. So every cell the loop reads has both indexes above 0, and those cells always have a real choice: Move.MATCH, Move.UP or Move.LEFT.

Exercise 5. What does the edit distance program print for an empty first word and the second word ab?

Show the answer

It prints distance = 2, then 1. insert a and 2. insert b. The top row has the choice Move.INSERT, and the walk back moves left twice. Each insert is added to the front of the deque, so the output ends up in the order a, then b.

Summary

• Store one choice for each cell while the value is being computed, in a table of the same size.
• Start the walk at the last cell, follow the stored choice, and stop at the border of the table.
• Use appendleft when the walk runs from the end to the start, so the output reads in order.
• Make the walk's loop condition match the border cells, so it never reads a choice that was never set.
• Keep the value and the choice in the same branch, so the walk always agrees with the number.