2-D Dynamic Programming

What it is

Two-dimensional dynamic programming (DP) solves a problem by storing answers to subproblems identified by two coordinates. Those coordinates might represent a grid cell, two sequence prefixes, or the endpoints of an interval.

The central idea is to replace repeated exploration with a table. A recursive search may reach the same subproblem through many different paths. DP evaluates that subproblem once and reuses its answer. Exponential branching often becomes polynomial work over a rectangular or triangular table.

The dimensions describe the subproblem, not necessarily the input. A single sequence can require a two-dimensional table indexed by interval endpoints. Conversely, a grid problem may require additional states if the future depends on information beyond the current cell.

How to recognize it

Look for these signals:

• Two progress coordinates: decisions consume elements from either of two ordered sequences.
• Restricted grid movement: each destination depends on previously reachable cells.
• Contiguous intervals: decisions remove endpoints, match endpoints, or split a range.
• Repeated choices: different decision histories leave the same remaining work.
• Optimization or counting: find a minimum cost, maximum score, number of routes, or number of optimal solutions.
• Small dependency neighborhoods: each answer can be built from a few smaller answers.

Check that the state contains everything needed for future decisions. If cost depends on whether a deletion run is already open, two indices alone are insufficient; add a small mode dimension.

The core technique

For every variant, define the state in a sentence before writing a recurrence. Then identify legal transitions, initialize boundary states, and choose an evaluation order in which every dependency is ready.

1. Grid states

Use dp[r][c] when the subproblem ends at, or is anchored at, a grid cell. With only rightward and downward movement, fill rows and columns in increasing order.

For route counting, add counts from legal predecessors. Initialize the starting cell to one and unreachable cells to zero. Other directed moves use the same principle: two forward-knight moves produce two predecessor coordinates rather than the usual upper and left neighbors. The traversal must still follow the dependency order.

For additive minimum cost, take the cheapest predecessor and add the current cell's cost. For a minimax objective—minimizing the largest cell rating encountered—extend a predecessor with max(previous_peak, current_rating), then minimize across predecessors. Initialize the start with its own rating; use infinity for unreachable states.

Some grid states describe shapes rather than paths. For the largest all-available square, let each state be the side length of the largest square ending at that cell:

def largest_square_side(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]
    best = 0
    for r in range(1, rows + 1):
        for c in range(1, cols + 1):
            if grid[r - 1][c - 1]:
                dp[r][c] = 1 + min(
                    dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]
                )
                best = max(best, dp[r][c])
    return best

All three neighboring squares must support the extension. Return best * best if the requested quantity is area.

2. Paired prefixes or suffixes

Use dp[i][j] for the first i elements of one sequence and first j elements of another. Transitions typically consume one element from either sequence, or one from each.

This models edit costs, alignment, and order-preserving interleavings. Interleaving transitions consume from exactly one sequence while preserving both internal orders. Alignment transitions may pair two elements, with a cost such as their absolute difference, or delete an element.

For longest common subsequence length, a suffix definition makes the recurrence especially direct:

def lcs_lengths(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            if a[i] == b[j]:
                dp[i][j] = 1 + dp[i + 1][j + 1]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
    return dp

Suffix states also support increasing mappings between sequences: either skip a candidate in the second sequence or pair it with the current element of the first. Empty-source states cost zero; states with too few remaining candidates are impossible. To reconstruct the lexicographically earliest optimal selected indices, repeatedly choose the earliest index that preserves the optimal suffix cost.

When counting optimal action strings, store both best cost and count. A strictly better transition replaces both; an equally good transition adds its count. This assumes transitions represent disjoint action strings.

Run-priced deletions require three modes per index pair: no open deletion run, deleting from the first sequence, and deleting from the second. Starting a run pays its opening cost; continuing it pays only its extension cost.

Counting distinct outputs differs from counting paths. Different alignment paths can produce the same subsequence. Canonical next-symbol transitions, using earliest feasible occurrences and suffix lengths, avoid counting the same longest subsequence repeatedly.

3. Interval states

Use dp[l][r] when decisions affect a contiguous range. Fill intervals by increasing length, because transitions usually shorten them.

For minimum weighted deletions that leave a palindrome, deleting either endpoint reduces the interval. Matching endpoints can both remain:

def palindrome_deletion_cost(s, weight):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for l in range(n - length + 1):
            r = l + length - 1
            dp[l][r] = min(
                weight[l] + dp[l + 1][r],
                weight[r] + dp[l][r - 1],
            )
            if s[l] == s[r]:
                inner = dp[l + 1][r - 1] if length > 2 else 0
                dp[l][r] = min(dp[l][r], inner)
    return dp

This assumes nonnegative deletion costs. The first row gives answers for every nonempty prefix.

For alternating endpoint-choice games, store the current player's optimal score difference. Each move contributes its removed values minus the opponent's optimal difference on the remaining interval. Taking one or two values from one end simply adds legal transitions.

Distinct palindromic-subsequence counting uses interval inclusion-exclusion. Equal-symbol boundaries create duplicate constructions; nearest equal-symbol positions identify the overlap. Counts can be split by odd and even length, with endpoint wrapping preserving parity.

Common mistakes

• Mixing prefix lengths with inclusive indices.
• Using zero for impossible minimum-cost states instead of infinity.
• Filling the table before dependencies are available.
• Counting decision paths when distinct resulting objects are requested.
• Omitting history, such as an open deletion run, from the state.
• Rolling rows before preserving every required neighbor.
• Choosing arbitrary optimal transitions when reconstruction requires a tie-breaking rule.

Complexity

A grid table typically costs O(RC) time and space. Paired-sequence DP usually costs O(nm); a constant number of modes changes only constant factors. Interval DP has O(n²) states and takes O(n²) time with constant work per state, or O(n³) when every split point is examined.

Local row dependencies often permit linear working space. Reconstruction, arbitrary interval access, or later destination queries may require retaining the full table. Counting with unbounded integers also introduces arithmetic costs that depend on the counts' bit lengths.