Two-dimensional dynamic programming

A second state dimension appears for a reason — two sequences, a remaining budget, a range, or a mode — and naming that reason is what makes the table's size and the recurrence's shape both predictable. This guide covers the grid recurrences and their border base cases, the sequence-alignment family from longest common subsequence to weighted edit distance, the knapsack table and the loop direction that separates the zero-one variant from the unbounded one, and interval formulations that must be filled in order of increasing length. Because memory rather than time is usually the binding constraint here, it also covers rolling rows, Hirschberg's linear-space reconstruction, and when a sparse memoised cache beats a dense table outright.

when a second dimension is needed

A second state dimension is required exactly when the answer depends on something a single index cannot summarise.

Two sequences need one index each; a budget constraint needs the remaining budget; a mode or parity needs the flag — each is a genuine dimension rather than a stylistic choice.

Name what the answer would be ambiguous about without it.

# dp[i]      - "best over the first i items"           : ambiguous once a budget exists
# dp[i][w]   - "...with w capacity left"               : now determined
# dp[i][j]   - "...aligning the first i of a, j of b"  : two sequences, two indices

Interview trap. Adding a dimension to make a wrong recurrence pass the samples hides the real defect, which is usually a missed transition case.

Engineering practice. Justify each dimension by naming what the answer would be ambiguous about without it.

the grid-path recurrence

Counting paths through a grid with movement restricted to two directions is the sum of the two predecessor cells.

The first row and column have exactly one path each, which are the base cases, and every other cell adds its two neighbours.

Border cells have exactly one path; zero makes the whole grid zero.

dp = [[0] * n for _ in range(m)]
for i in range(m): dp[i][0] = 1
for j in range(n): dp[0][j] = 1
for i in range(1, m):
    for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1]

# 3 x 7 grid -> 28 paths

Interview trap. Initialising the whole first row and column to zero rather than one gives a total of zero across the entire grid.

Engineering practice. Set the base row and column explicitly, and check the one-by-one and one-by-n cases.

obstacles and unreachable cells

An obstacle sets a cell's value to zero and, crucially, terminates the base-case run along a border rather than merely skipping one cell.

Every cell after an obstacle in the first row is unreachable, so the base-case loop must stop rather than continue past it.

Stop the border loop at the first obstacle.

for j in range(n):
    if grid[0][j] == 1: break        # everything after is unreachable
    dp[0][j] = 1

Skipping only the blocked cell leaves later border cells reachable when they are not.

Interview trap. Skipping just the obstacle cell in the border initialisation leaves later border cells reachable when they are not.

Engineering practice. Break out of the border loop at the first obstacle, and test a grid whose first row is blocked halfway.

minimum-cost paths

Minimum path sum replaces the addition of the counting recurrence with a minimum over the same predecessors.

The structure of the recurrence is identical, and only the combining operator and the base value change.

Use the operator's identity, not zero.

dp = [[float("inf")] * n for _ in range(m)]    # inf for a minimum, not 0
dp[0][0] = grid[0][0]

Interview trap. Reusing zero as the initial value for a minimisation makes every cell zero, since zero is the identity for addition, not for minimisation.

Engineering practice. Use the operator's identity — infinity for a minimum, negative infinity for a maximum — as the initial value.

longest common subsequence

The longest common subsequence of two sequences is computed on a table indexed by prefixes of each, in time proportional to their product.

Matching characters extend the diagonal predecessor by one, and mismatching ones take the better of dropping one character from either sequence.

Match extends the diagonal; mismatch takes the better neighbour.

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
        else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

# "abcde" / "ace" -> 3. Substring would reset to 0 on a mismatch and give 1.

Interview trap. Confusing subsequence with substring gives a different and simpler problem, and the two recurrences are not interchangeable.

Engineering practice. State whether contiguity is required, and use the diagonal-reset recurrence for substrings and the diagonal-extend one for subsequences.

edit distance

Levenshtein distance is a table over prefixes where each cell takes the cheapest of insertion, deletion, and substitution.

The base row and column are the costs of building each prefix from nothing, which are the prefix lengths.

The base row and column are the prefix lengths.

for i in range(m + 1): dp[i][0] = i          # i deletions
for j in range(n + 1): dp[0][j] = j          # j insertions
...
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (a[i-1] != b[j-1]))

# "horse" -> "ros" is 3

Interview trap. Initialising the base row and column to zero makes empty-to-nonempty transformations free, and the resulting distances are all too small.

Engineering practice. Fill the base row and column with the prefix lengths, and validate against a known pair whose distance is documented.

weighted edit operations

When insertion, deletion, and substitution have different costs, the recurrence is unchanged but the resulting metric may no longer be symmetric.

Asymmetric costs mean the distance from one string to another differs from the reverse, which breaks any code assuming a metric.

Asymmetric costs break the metric; key any cache by the ordered pair.

COST = {"insert": 1, "delete": 5, "substitute": 2}
# d("ab", "abc") = 1 (insert), d("abc", "ab") = 5 (delete).
# A cache keyed on frozenset({a, b}) returns the wrong direction.

Interview trap. Caching distances in a symmetric structure under asymmetric costs returns the wrong direction's value.

Engineering practice. State whether the cost model is symmetric, and key any cache by the ordered pair when it is not.

the zero-one knapsack table

The two-dimensional knapsack state is the item index and the remaining capacity, and the transition is take-or-skip.

Taking an item consults the previous item's row at the reduced capacity, which is what prevents reusing the same item.

Read the previous row, or an item can be reused.

for i in range(1, n + 1):
    for w in range(W + 1):
        dp[i][w] = dp[i-1][w]                                   # skip
        if wt[i-1] <= w:
            dp[i][w] = max(dp[i][w], dp[i-1][w - wt[i-1]] + val[i-1])   # previous row

Interview trap. Consulting the current row instead of the previous one allows unlimited reuse, converting the problem into the unbounded variant.

Engineering practice. Reference the previous row explicitly, and test with an instance where reuse would yield a better but invalid answer.

collapsing the knapsack to one dimension

The knapsack table collapses to a single array when capacities are iterated downward.

Downward iteration guarantees each entry still holds the previous item's value when it is read, which reproduces the two-row semantics in one array.

Iterate capacities downward for the zero-one variant.

for i in range(n):
    for w in range(W, wt[i] - 1, -1):        # downward: each item once
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
# Upward instead turns this into the unbounded knapsack, silently.

Interview trap. Iterating upward after collapsing silently converts the zero-one problem into the unbounded one.

Engineering practice. Tie the loop direction to the item semantics in a comment, and keep a two-row version as the reference in tests.

partition and subset-sum problems

Deciding whether a subset sums to a target is a boolean knapsack, and equal partition is that with the target set to half the total.

An odd total makes equal partition immediately impossible, which is a constant-time check before any table is allocated.

Check parity before allocating anything.

total = sum(a)
if total % 2: return False        # O(1) - no table needed
target = total // 2

Interview trap. Building the table before checking parity wastes the whole computation on an instance that is trivially infeasible.

Engineering practice. Apply the cheap infeasibility checks first, and only then allocate the table.

interval dynamic programming

Problems whose subproblems are ranges are indexed by the two endpoints and solved in order of increasing range length.

The transition splits the range at every interior point, which adds a factor proportional to the range length and gives a cubic bound.

Loop over length outermost, then the left endpoint.

for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(i, k, j) for k in range(i, j))

Iterating by left endpoint reads sub-ranges that are not computed yet.

Interview trap. Iterating by left endpoint rather than by length reads sub-ranges that have not been computed yet.

Engineering practice. Loop over length outermost, then over the left endpoint, so every sub-range is already final.

matrix-chain multiplication

The optimal parenthesisation of a matrix product is an interval dynamic program over the chain, with a cubic bound.

Each split point is tried, and the cost combines the two sub-chains plus the cost of the final multiplication implied by the dimensions.

Try every split; greedy is not optimal.

# Dimensions 10x30, 30x5, 5x60:
# (AB)C = 10*30*5 + 10*5*60  = 1,500 + 3,000 = 4,500
# A(BC) = 30*5*60 + 10*30*60 = 9,000 + 18,000 = 27,000

Interview trap. Optimising by a greedy rule such as always multiplying the smallest pair first is not optimal, and small counterexamples show it.

Engineering practice. Use the interval formulation, and store the split points if the parenthesisation itself must be reported.

palindromic substrings

Palindrome tables are interval dynamic programs where a range is a palindrome when its ends match and its interior is one.

The dependency is on the shorter interior range, so the iteration must again proceed by increasing length.

Expanding around centres is the same O(n^2) in O(1) space.

def longest(s):
    best = ""
    for c in range(len(s)):
        for lo, hi in ((c, c), (c, c + 1)):        # odd and even centres
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]: lo -= 1; hi += 1
            if hi - lo - 1 > len(best): best = s[lo+1:hi]
    return best

Interview trap. Assuming the table is required to find the longest palindromic substring misses that expanding around each centre achieves the same quadratic time in constant space.

Engineering practice. Prefer expansion around centres when only the longest palindrome is needed, and use the table when many range queries follow.

state compression with bitmasks

When one dimension is a subset of a small set, it is encoded as an integer bitmask and the table is indexed by it directly.

This makes the state count two to the n times whatever else the state carries, which is practical only for n around twenty.

2^n x n states - compute the memory first.

# n = 20: 1,048,576 x 20 x 8 bytes = 168 MB
# n = 24: 16,777,216 x 24 x 8 bytes = 3.2 GB

Interview trap. Reaching for a bitmask on a set larger than about twenty elements produces a table that cannot be allocated.

Engineering practice. Compute the state count first, and switch to approximation or a different formulation when it exceeds memory.

digit dynamic programming

Counting numbers in a range with a digit property is a dynamic program over digit positions with a tight-bound flag.

The flag records whether the prefix built so far equals the bound's prefix, which decides whether the next digit is unrestricted.

Carry the tight flag and the leading-zero flag.

@cache
def go(pos, tight, started, state):
    if pos == len(digits): return int(started)
    limit = digits[pos] if tight else 9
    total = 0
    for d in range(0, limit + 1):
        next_started = started or d > 0
        next_value = next_state(state, d) if next_started else state
        total += go(pos + 1, tight and d == limit, next_started, next_value)
    return total

Without tight the count includes numbers above the bound; without preserving state across leading zeros, shorter numbers acquire digits they never had.

Interview trap. Omitting the tight flag counts numbers above the bound, and omitting a leading-zero flag miscounts shorter numbers.

Engineering practice. Carry both flags explicitly, and verify against brute-force counting for bounds up to a few thousand.

the transition cost factor

Two-dimensional dynamic programs often have a transition that loops, making the total cubic rather than quadratic.

The bound is the state count times the transition cost, so a linear transition over a quadratic state space gives a cubic algorithm.

n^2 states with an O(n) split is O(n^3).

# n = 500: 250,000 states x 500 splits = 125,000,000 operations - seconds in C,
# minutes in Python. n = 2,000 is 8 x 10^9: out of reach either way.

Interview trap. Reporting the complexity as the table size ignores the inner loop, which is usually the dominant factor.

Engineering practice. Quote both factors, and look for a monotonic or convex structure that lets the inner loop be replaced by a pointer or a deque.

monotonic optimisation of transitions

When the optimal split point is monotone in the state, the inner loop can be amortised away, reducing a cubic algorithm to quadratic.

Divide-and-conquer optimisation and the Knuth condition both exploit that the optimal split does not move backwards as the range grows.

Verify the condition, then validate against the plain version.

# Divide-and-conquer optimisation requires opt(i, j) to be monotone in j.
# Apply it unverified and the algorithm is faster and wrong, with no error.
assert dp_optimised(case) == dp_plain(case)     # on thousands of random small cases

Interview trap. Applying the optimisation without verifying the monotonicity condition produces a faster and wrong algorithm.

Engineering practice. Verify the condition on the cost function, and validate the optimised version against the plain one on random inputs.

memory as the binding constraint

A two-dimensional table's memory is the product of its dimensions, which becomes the limit long before time does.

A table over two ten-thousand-element sequences holds a hundred million entries, which exceeds typical memory budgets at four or eight bytes each.

Two 10,000-character sequences is 10^8 cells.

# 10,000 x 10,000 x 4 bytes = 400 MB for the table alone.
# The time bound, 10^8 operations, is the easy part.

Interview trap. Estimating feasibility from the time bound alone leads to an implementation that cannot allocate its table.

Engineering practice. Compute the memory before implementing, and apply the rolling-row reduction when only the final value is needed.

rolling rows

When a row depends only on the previous one, two rows suffice and memory drops from the product to one dimension.

The rows are swapped each iteration, or a single array is updated in an order that preserves the needed previous values.

Two rows instead of m, and the alignment is gone.

prev = [0] * (n + 1)
for i in range(1, m + 1):
    cur = [0] * (n + 1)
    for j in range(1, n + 1): cur[j] = ...
    prev = cur                     # O(n) memory instead of O(mn)

Interview trap. The reduction discards the intermediate rows, so the alignment or choice sequence can no longer be reconstructed.

Engineering practice. Use rolling rows for the value, and keep the full table or use Hirschberg's divide-and-conquer method when the alignment is needed.

Hirschberg's reduction

An optimal alignment can be reconstructed in linear space by combining the rolling-row evaluation with divide and conquer.

The middle column's optimal crossing point is found from a forward and a backward linear-space pass, and the two halves are solved recursively.

Linear space and the alignment, via divide and conquer.

# Forward pass over the first half, backward pass over the second, both in O(n) space.
# The optimal crossing point of the middle column joins them; recurse on both halves.
# With 4-byte cells, time stays O(mn); memory drops from 400 MB to about 80 KB
# for 10,000 x 10,000. Managed-language object overhead can make both figures larger.

Interview trap. Assuming linear space forces losing the alignment is the misconception this technique exists to correct.

Engineering practice. Reach for it when sequences are long enough that the full table does not fit but the alignment is still required.

top-down on large sparse state spaces

Memoisation is preferable when only a small fraction of the state space is reachable.

A dictionary-keyed cache allocates only for visited states, whereas a dense table allocates for all of them regardless of reachability.

Allocate for reachable states only.

@cache
def f(i, w): ...
# Dense table: 1,000 x 1,000,000 = 10^9 cells.
# Reachable states from the actual weights: often a few hundred thousand.

Interview trap. Allocating a dense table for a sparse reachable set can exhaust memory on a problem the top-down version handles comfortably.

Engineering practice. Estimate reachability, and choose the sparse cache when it is a small fraction of the full space.

recursion depth in two dimensions

Top-down two-dimensional solutions recurse to a depth proportional to the sum of the dimensions.

Two sequences of five thousand characters give a chain of ten thousand calls, which exceeds default recursion limits.

Depth is m + n, not log of anything.

f(5_000, 5_000)     # 10,000 nested calls: RecursionError

Interview trap. Raising the limit converts a clean failure into a native stack overflow rather than fixing anything.

Engineering practice. Use tabulation when the dimensions are large, and reserve memoisation for sparse or shallow state spaces.

index conventions

Prefix-indexed tables usually have one more row and column than the sequence lengths, because the empty prefix is a state.

The extra row and column hold the base cases, which is what removes the special-casing from the main loop.

Size to length + 1 and read i as 'the first i characters'.

dp = [[0] * (n + 1) for _ in range(m + 1)]     # row 0 and column 0 hold the base cases
# a[i-1] is the character that dp[i] refers to - stated once, used everywhere.

Interview trap. Sizing the table to the sequence lengths forces the base cases into the loop and produces off-by-one errors throughout.

Engineering practice. Size tables to length plus one and treat index i as 'the first i characters', keeping the convention in a comment.

reconstructing two-dimensional solutions

Walking backwards through the table from the final cell recovers the choices, provided the table was retained.

At each cell, the predecessor that achieved the recorded value identifies the decision, and ties are broken by a documented rule.

Ties give different valid answers; assert the value.

i, j, out = m, n, []
while i and j:
    if a[i-1] == b[j-1]: out.append(a[i-1]); i -= 1; j -= 1
    elif dp[i-1][j] >= dp[i][j-1]: i -= 1     # a different tie rule gives another
    else: j -= 1                              # equally optimal subsequence

Interview trap. Different tie-breaking gives different valid answers, so tests must accept any optimal solution rather than one specific string.

Engineering practice. Assert the optimal value and the validity of the reconstruction rather than a fixed sequence.

choosing the formulation

The formulation follows from what the subproblem is: prefixes of two sequences, a range, a subset, or a position plus a budget.

Naming the subproblem gives the dimensions, the dimensions give the memory, and the transition gives the remaining factor.

The subproblem sentence gives the dimensions, and the dimensions give the memory.

Subproblem	State	Cells
prefixes of two sequences	(i, j)	m x n
a contiguous range	(i, j), i <= j	n^2 / 2
a subset of a small set	bitmask	2^n
position plus budget	(i, b)	n x B

Interview trap. Starting from the code shape of a remembered problem rather than from the subproblem is how a solution ends up with the wrong dimensions.

Engineering practice. Write the subproblem sentence first, derive the table from it, and only then estimate whether it fits.