Dynamic Programming: 2D

Updated Nov 19, 2026 · 4 min read
On this page

    Two-dimensional DP is the same method as DP 1D, with one more number in the state. A subproblem is now "the first i characters of one string and the first j of the other", or "the cell at row r, column c", or "the substring from i to j". The table is a grid, and each cell is filled from a few neighbours that are already done.

    When to recognise it

    • A grid with "number of paths", "minimum path sum", "largest square": dp[r][c] comes from the cell above and the cell to the left.
    • Two strings or sequences: longest common subsequence, edit distance, interleaving, wildcard or regex matching. dp[i][j] covers a[:i] and b[:j].
    • A substring or range of one string: longest palindromic substring or subsequence, burst balloons. dp[i][j] covers s[i..j], filled by increasing length.
    • Knapsack: items × capacity. "Can I pick items summing to target?" (partition equal subset sum) is a 2D table that is usually squeezed into one row.

    Shape 1: grid paths

    Paths into a cell = paths from above + paths from the left. Walls contribute 0.

    A 3 by 3 grid with a wall in the middle. The path counts are 1, 1, 1 / 1, wall, 1 / 1, 1, 2: the bottom-right cell adds 1 from above and 1 from the left.
    A 3 by 3 grid with a wall in the middle. The path counts are 1, 1, 1 / 1, wall, 1 / 1, 1, 2: the bottom-right cell adds 1 from above and 1 from the left.
    def unique_paths(grid):
        """Grid DP: paths into a cell = paths from above + paths from the left. '#' is a wall."""
        rows, cols = len(grid), len(grid[0])
        dp = [[0] * cols for _ in range(rows)]
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '#':
                    continue
                if r == 0 and c == 0:
                    dp[r][c] = 1
                    continue
                dp[r][c] = (dp[r - 1][c] if r else 0) + (dp[r][c - 1] if c else 0)
        return dp[-1][-1]

    Time and space O(rows × cols). Only the previous row is needed, so one row of length cols is enough.

    Shape 2: two strings

    Make the table one row and one column bigger than the strings. Row 0 and column 0 stand for the empty prefix, and they hold the base cases.

    Edit distance table for "horse" (rows) and "ros" (columns). Row 0 is 0, 1, 2, 3 and column 0 is 0 to 5. Each cell looks at the cell up-left (replace, or free if the letters match), up (delete) and lef
    Edit distance table for "horse" (rows) and "ros" (columns). Row 0 is 0, 1, 2, 3 and column 0 is 0 to 5. Each cell looks at the cell up-left (replace, or free if the letters match), up (delete) and left (insert). The bottom-right cell is 1 + min(3, 2, 4) = 3.
    def lcs(a, b):
        """Two-string DP: dp[i][j] = answer for a[:i] and b[:j]. Row 0 and column 0 are empty prefixes."""
        dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
        for i in range(1, len(a) + 1):
            for j in range(1, len(b) + 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[-1][-1]

    Edit distance has the same shape with three choices. Each row only reads the row above, so this version keeps one previous row:

    def edit_distance(a, b):
        """Same table shape. Base cases: turning a prefix into '' costs its length."""
        prev = list(range(len(b) + 1))          # row i-1, kept as one array to save space
        for i in range(1, len(a) + 1):
            cur = [i] + [0] * len(b)
            for j in range(1, len(b) + 1):
                if a[i - 1] == b[j - 1]:
                    cur[j] = prev[j - 1]
                else:
                    cur[j] = 1 + min(prev[j - 1],   # replace
                                     prev[j],       # delete a[i-1]
                                     cur[j - 1])    # insert b[j-1]
            prev = cur
        return prev[-1]

    Time O(m × n), space O(n) with the rolling row.

    Shape 3: substrings

    For substrings, dp[i][j] depends on dp[i + 1][j − 1], the shorter range inside it, so you fill by increasing length. For the longest palindromic substring there is a simpler O(n²) method with O(1) space: treat each of the 2n − 1 centres as the middle and expand outward while the ends match.

    def longest_palindrome(s):
        """Interval DP alternative: expand around each of the 2n - 1 centres, O(n^2) time, O(1) space."""
        best = ''
        for centre in range(2 * len(s) - 1):
            lo, hi = centre // 2, centre // 2 + centre % 2
            while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
                lo, hi = lo - 1, hi + 1
            if hi - lo - 1 > len(best):
                best = s[lo + 1:hi]
        return best

    Mention both: the table version shows the DP idea, and expanding around centres is what you'd actually write.

    How to fill the table without mistakes

    1. Say the state in a sentence: "dp[i][j] is the edit distance between a[:i] and b[:j]."
    2. Fill row 0 and column 0 from that sentence (turning a prefix into the empty string costs its length).
    3. Write the recurrence for one inner cell, with the letters a[i − 1] and b[j − 1].
    4. Check one cell by hand on a tiny example before coding the loops.

    Common bugs

    • Index shift: dp has one extra row and column, so the characters are a[i − 1] and b[j − 1]. Mixing these is the most common 2D bug.
    • Building rows with [[0] * n] * m in Python: every row is the same list. Use a list comprehension.
    • Wrong fill order for substrings: looping i upward reads dp[i + 1][…] before it is filled. Loop by length, or i downward.
    • Rolling arrays overwriting values you still need: for LCS with one row, save the old diagonal value before you overwrite it.
    • Mixing up subsequence and substring: a subsequence may skip characters, a substring may not. The recurrences differ.

    Say this in the interview

    • "Let dp[i][j] be the answer for the first i letters of a and the first j letters of b. If the last letters match, it's dp[i − 1][j − 1]; otherwise I try each operation and take the best."
    • "Each cell takes O(1), so O(m × n) time. Each row only needs the one above, so I can cut space to O(n)."

    Problems for this pattern

    1. Unique Paths: grid paths.
    2. Longest Common Subsequence: two strings.
    3. Longest Palindromic Substring: substrings, or expand around centres.
    4. Partition Equal Subset Sum: knapsack in one row.
    5. Maximal Square: 1 + min of three neighbours.
    6. Edit Distance: two strings, three choices.
    7. Regular Expression Matching: two strings with a star rule, the hard one.

    Related

    DP 1D · Backtracking · Arrays and Strings · Pattern Recognition Cheat Sheet