Dynamic Programming, in depth: filling the table cell by cell, legal fill orders and reconstructing the answer

The four parts of every DP table

Every tabulated DP has four parts. Getting each one explicit before writing code removes most bugs.

1. The state space. The set of subproblems, each named by a small tuple such as (row, column) or (i, j) or (item, capacity). The table is just an array indexed by that tuple. Its size is the number of states, and that number times the work per state is your running time.
2. The stencil. For a single cell, the list of other cells its recurrence reads. In the grid example below, cell (r, c) reads (r-1, c) and (r, c-1). The stencil is a fixed shape that slides over the table, and it decides everything about which fill orders are legal.
3. The boundary. The cells whose stencil would read outside the table. They need either base values or a guard. Boundary mistakes are the most common DP bug, ahead of wrong recurrences.
4. The fill order. Any order that visits each cell after every cell in its stencil. Formally the states and stencil edges form a directed acyclic graph, and a fill order is a topological order of it.

A fifth part is optional but almost always wanted: a parent record that remembers which stencil neighbour won each cell, so that the optimal decisions can be replayed after the table is full.

Worked example: filling a grid frame by frame

Take a 3 by 4 grid of costs. You start at the top-left, may move only right or down, and want the cheapest path to the bottom-right, where a path's cost is the sum of the cells it visits. The costs are:

1 3 1 2
1 5 1 3
4 2 1 1

State: dp[r][c] is the cheapest cost of any path from (0, 0) that ends at (r, c). Recurrence: you reach (r, c) either from above or from the left, so dp[r][c] = cost[r][c] + min(dp[r-1][c], dp[r][c-1]). Boundary: dp[0][0] = cost[0][0]; the top row can only be reached from the left and the left column only from above.

Now fill it the way an animation would, one cell per frame, in row-major order. Frame 1 writes 1. Frames 2 to 4 run along the top row, adding each cost to its left neighbour: 4, 5, 7. Frame 5 starts row 1 at the left edge: 1 + 1 = 2. Frame 6 is the first cell with a real choice: cost 5 plus min(4 above, 2 left) gives 7. Frame 7: 1 + min(5, 7) = 6, taking the value from above. Frame 8: 3 + min(7, 6) = 9. Row 2 goes 2 + 4 = 6 at the edge, then 2 + min(7, 6) = 8, then 1 + min(6, 8) = 7, and finally 1 + min(9, 7) = 8.

Two observations generalise. First, every value is final when written; DP never revisits a cell, which is what separates it from iterative relaxation methods like Bellman-Ford. Second, the bottom-right value 8 is only a cost. To show the user which path costs 8 you need reconstruction, which is a second walk over the same table.

Reconstruction: getting the decisions back

Reconstruction starts at the answer cell and repeatedly steps to the stencil neighbour that produced the winning value. From (2, 3) with value 8 the candidates were 9 above and 7 to the left, so the path came from the left. At (2, 2) the candidates were 6 above and 8 left, so it came from above, and so on back to (0, 0). Reversing the walk gives right, right, down, down, right. You can recompute the winner from the table, or store it while filling. Storing costs memory but removes any chance that the forward and backward passes disagree on ties.

def min_path(cost):
    R, C = len(cost), len(cost[0])
    INF = float("inf")
    dp = [[INF] * C for _ in range(R)]
    parent = [[None] * C for _ in range(R)]
    for r in range(R):                      # row-major: up and left are done
        for c in range(C):
            if r == 0 and c == 0:
                dp[r][c] = cost[r][c]
                continue
            up = dp[r - 1][c] if r > 0 else INF
            left = dp[r][c - 1] if c > 0 else INF
            if up <= left:                  # tie rule is explicit and shared
                dp[r][c], parent[r][c] = cost[r][c] + up, "D"
            else:
                dp[r][c], parent[r][c] = cost[r][c] + left, "R"
    moves, r, c = [], R - 1, C - 1
    while parent[r][c] is not None:
        step = parent[r][c]
        moves.append(step)
        if step == "D":
            r -= 1
        else:
            c -= 1
    return dp[R - 1][C - 1], moves[::-1]

print(min_path([[1, 3, 1, 2], [1, 5, 1, 3], [4, 2, 1, 1]]))
# (8, ['R', 'R', 'D', 'D', 'R'])

The parent table records the move that arrived at each cell: D means the cell was entered from above, R from the left. Notice the use of infinity for out-of-range neighbours instead of special-casing the first row and column. Padding the boundary with a neutral value (infinity for a minimum, zero for a count, negative infinity for a maximum) shrinks the boundary logic to one place and is the single most effective habit for avoiding off-by-one errors.

Fill orders follow from the stencil

Row-major order is not special. It is legal here because the stencil points only up and left. Change the stencil and the legal orders change with it.

• Column-major also works for the grid: walking down each column still finishes up and left first. Choosing between row-major and column-major is then a cache question; in a row-major array in C, Java or NumPy, walking along rows touches memory sequentially.
• Anti-diagonal (wavefront). All cells with the same r + c depend only on the previous diagonal, so a whole diagonal can be computed in parallel. This is how GPU and SIMD implementations of sequence alignment get their speed, and it is the order to reach for when one table is large enough to justify parallel hardware.
• By interval length. Problems over substrings, such as longest palindromic subsequence, define dp[i][j] over the range i..j and read dp[i+1][j-1], dp[i+1][j] and dp[i][j-1]. Those are shorter intervals, so the legal order is all length-1 intervals, then length 2, and so on. Row-major from the top is wrong here, because dp[0][4] would read dp[1][3] before row 1 exists. Iterating i from the bottom row upward and j left to right is an equivalent legal order.
• By item, then capacity. In 0/1 knapsack row k reads only row k-1, which is what makes the one-row space optimisation possible, provided capacity is scanned from high to low so each item is used at most once. Scanning low to high silently turns it into the unbounded version, which is exactly the distinction drawn in the two coin change variants.

Memory: rolling arrays and what they cost

The stencil also tells you how much of the table you must keep. If every cell reads only the current and previous row, two rows suffice, and for the grid one row is enough because the left neighbour is in the row being written and the upper neighbour is the old value at the same index. That cuts memory from R times C to C.

The price is reconstruction. Once rows are overwritten, the parent walk has nothing to read. Three ways out, in rising order of effort:

• Keep a compact parent table of one byte or even two bits per cell while using a rolling array for values. For a 10,000 by 10,000 alignment that is 100 MB of bytes instead of 800 MB of 64-bit values.
• Checkpoint every k-th row during the forward pass and recompute the band you need during the backward walk. Memory drops by a factor of k and time roughly doubles.
• Use Hirschberg's divide-and-conquer technique, which finds the middle cell of the optimal path with two linear-space passes and recurses on the halves. It reconstructs the full path in linear space for about twice the time, and is the standard answer for long-sequence LCS and alignment.

Debugging a DP with brute force

A wrong DP usually fails quietly: it returns a plausible number. The fastest way to catch it is to write a brute force that is obviously correct, run both on thousands of small random inputs, and print the first disagreement together with both tables.

import itertools, random

def brute(cost):
    R, C = len(cost), len(cost[0])
    best = float("inf")
    for downs in itertools.combinations(range(R + C - 2), R - 1):
        r = c = 0
        total = cost[0][0]
        for k in range(R + C - 2):
            if k in downs:
                r += 1
            else:
                c += 1
            total += cost[r][c]
        best = min(best, total)
    return best

for trial in range(5000):
    R, C = random.randint(1, 5), random.randint(1, 5)
    g = [[random.randint(0, 9) for _ in range(C)] for _ in range(R)]
    assert min_path(g)[0] == brute(g), g

Small sizes matter: 1 by 1, 1 by n and n by 1 grids exercise the boundary code that hand-written tests skip. Also check that the reconstructed moves, replayed on the grid, sum to the reported cost. That one assertion catches parent-table bugs that the value check cannot see. When the check fails, printing the table cell by cell in fill order (the same view as the diagram above) usually shows the bad cell in seconds.

Failure modes

The failure modes below cover most broken DP tables seen in code review.

The last row deserves a word. A DP over (item, remaining capacity) runs in time proportional to the capacity value, not its number of digits. That is pseudo-polynomial: fine for a capacity of 10,000, hopeless for 10 to the power 12. If the table would not fit in memory, the problem needs a different state, a meet-in-the-middle split or an approximation, not a cleverer fill order.

Trade-offs: tabulation versus memoisation

Tabulation with an explicit fill order is not always the right tool. Memoised recursion visits only reachable states, which wins when the reachable set is a small fraction of the full table, as in many game and parsing problems. It costs recursion depth and hash lookups, and Python's default recursion limit of 1,000 frames is reached quickly. Tabulation visits every state, has predictable memory access, enables rolling arrays and wavefront parallelism, and is the version you want for performance-critical code. A sensible workflow is to prototype top-down, confirm against brute force, then convert to a table once the state space and stencil are clear, because the stencil is easy to read off a working memoised function: it is the set of recursive calls.

What to do next

• Take one DP you already know and write down its state tuple, stencil, boundary and a legal fill order before touching code. If you cannot name the stencil, you do not yet understand the recurrence.
• Re-implement the grid example with a parent table, then replace the value table with a single rolling row while keeping a one-byte parent table, and confirm the reconstructed path is unchanged.
• Solve longest palindromic subsequence twice, once with a deliberately wrong row-major fill, and watch the brute-force harness catch it.
• Add a randomised brute-force cross-check to every DP you ship, with inputs small enough that the brute force runs in milliseconds, and include 1 by n and empty-input cases.
• For a large two-sequence table, try the anti-diagonal order and measure whether vectorising a diagonal pays off on your hardware.