Pattern 14 of 20

2-D Dynamic Programming

Two indices define the state: grids, two strings, or items against capacity.

When to use it

Comparing two strings (edit distance, common subsequence)
Paths through a grid with choices at each cell
Knapsack-style limits: items against a budget

The idea

The state is a pair, so the table is a grid and each cell depends on its neighbours above and to the left. Filling it in the right order, and keeping only one row when possible, is the whole craft.

Typical cost O(m·n) time, O(n) space with a rolling row.

How it works

Two-dimensional DP needs two indices to describe a subproblem: a position in each of two strings, a cell in a grid, an item and a remaining capacity, or the start and end of an interval. The table dp[i][j] holds the answer for that pair.

For two strings, dp[i][j] usually means the answer for the first i characters of one and the first j of the other. The recurrence looks at the last characters: if they match, extend dp[i-1][j-1]; if not, take the best of dropping one character from either side. Edit distance, longest common subsequence and interleaving strings all follow that shape.

Grid paths are the most visual version: each cell is reached from the cell above or to the left, so dp[r][c] combines those two. Knapsack is the same structure over items and capacity.

Since each row usually depends only on the previous row, the table can shrink to one or two rows. Interval DP (best answer on the substring i..j) is the harder variant: fill it by increasing length so shorter intervals are ready first.

How to attack it

1Name both dimensions and define dp[i][j] in one sentence.
2Add an extra row and column for empty prefixes if strings are involved.
3Write the recurrence from the last decision (last characters, last cell, last item).
4Choose the fill order that makes every dependency available.
5Reduce space to one row once the full table version is correct.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def lcs_length(a, b):
    # dp[i][j] = LCS of a[:i] and b[:j]; row 0 and column 0 are empty prefixes.
    n, m = len(a), len(b)
    dp = [[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]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]


def grid_paths(grid):
    # One row of state: row[c] = ways to reach (r, c); 1 marks an obstacle.
    cols = len(grid[0])
    row = [0] * cols
    row[0] = 1
    for r in range(len(grid)):
        for c in range(cols):
            if grid[r][c] == 1:
                row[c] = 0
            elif c > 0:
                row[c] += row[c - 1]   # from above (old row[c]) + from left
    return row[-1]

Variants

Two strings: LCS, edit distance, interleaving and wildcard matching: compare the last characters of the two prefixes.
Grid paths: Count paths or minimize cost moving right and down; each cell reads its top and left neighbors.
0/1 knapsack: Items by capacity; with one row, iterate capacity downward so each item is used at most once.
Interval DP: dp[i][j] over a substring or subarray, filled by increasing length: palindromic substrings, burst balloons.
Index plus small state: A second dimension for a count or a flag, such as transactions left in stock problems.

Pitfalls

Indexing the strings with i and j instead of i - 1 and j - 1 when the table has the extra empty row.
Creating rows in Python with [[0] * m] * n, which aliases every row to the same list.
Iterating capacity upward in a one-row 0/1 knapsack, which silently reuses items.
Filling an interval table row by row instead of by length.
Overwriting a value in the one-row version before the next cell has read it (keep a 'diagonal' variable).

What it costs

Operation	Cost
Full table over n × m states	O(n · m) time and space
Rolling one row	O(n · m) time, O(m) space
0/1 knapsack	O(items × capacity)
Interval DP	O(n²) states, often O(n³) with a split point

45 2-D Dynamic Programming problems

Easiest first. Problems marked Free can be solved without Pro.

Solve them in the browser, in Python or JavaScript.

Start free See pricing