DP — Grid & Strings

TL;DR

When the brute-force solution recurses on two moving indices — one walking each of two strings, or row and column on a grid — you’re in 2D DP territory. The state is dp[i][j], the answer to the subproblem “best result for the first i characters of A versus the first j of B” or “best result to reach cell (i, j)”. Fill the table bottom-up so every cell only reads cells above it and to its left.

The transition is almost always one of three flavors. Grid path counting: dp[i][j] comes from dp[i-1][j] and dp[i][j-1] — sum them for path counts, take the min for path-cost problems. Two-string alignment (LCS, edit distance): if the characters match, take dp[i-1][j-1] plus a bonus; if not, take the best of skipping one side (dp[i-1][j]) or the other (dp[i][j-1]). Palindromic subsequence: dp[i][j] over a substring range — expand from a center, or fill the table on the diagonal.

If you can name which of those three transitions fits, you’re 80% done. The rest is base cases and indexing.

When to reach for it

Signals that 2D DP is the right move:

• The recursion you’d write naturally takes two indices that each move monotonically — i over string A, j over string B; or (row, col) on a grid.
• The problem compares two sequences and asks for similarity, edit cost, or a longest-common-something.
• You’re counting paths or summing costs through a grid where each step is constrained (right/down only, or up/left/diagonal).
• The question is “longest substring/subsequence with property X” and X depends on a pair of endpoints.

Signals it’s not this pattern: a single index suffices (1D DP), the state needs to remember a set or order of past picks (knapsack-with-history, TSP — those need bitmask DP), or the answer requires lookahead that can’t be expressed as “best of cells above and to the left”.

Flavor 1 — Longest Common Subsequence (LC 1143)

Given two strings, return the length of the longest subsequence common to both. A subsequence preserves order but allows gaps.

def lcs(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[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[m][n]

dp[i][j] is the LCS length using the first i chars of text1 and first j of text2. Row 0 and column 0 are zeros — empty prefix has nothing in common with anything. The i - 1 / j - 1 indexing is the off-by-one trap: the dp table is 1-indexed so we have a clean base row, but the strings stay 0-indexed.

Worked example. text1 = "abcde", text2 = "ace". Build the (5+1) by (3+1) table.

Trace the interesting cells. dp[1][1]: 'a' == 'a', so dp[0][0] + 1 = 1. dp[3][2]: 'c' == 'c', so dp[2][1] + 1 = 2. dp[5][3]: 'e' == 'e', so dp[4][2] + 1 = 3. The mismatches just inherit the bigger of left or up. Answer: dp[5][3] = 3, matching the subsequence “ace”.

Flavor 2 — Edit Distance (LC 72)

Minimum number of insert / delete / replace operations to turn word1 into word2.

def edit_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i        # delete every char in word1[:i]
    for j in range(n + 1):
        dp[0][j] = j        # insert every char in word2[:j]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete from word1
                    dp[i][j - 1],      # insert into word1
                    dp[i - 1][j - 1],  # replace
                )
    return dp[m][n]

Base cases matter here: dp[i][0] = i because turning any prefix into the empty string costs one delete per character; symmetrically for the top row.

Worked example. word1 = "horse", word2 = "ros". Table is 6 by 4.

Cell dp[2][2] (prefix “ho” → “ro”): 'o' == 'o', inherit dp[1][1] = 1. Cell dp[5][3] (prefix “horse” → “ros”): 'e' != 's', so 1 + min(dp[4][3], dp[5][2], dp[4][2]) = 1 + min(2, 3, 3) = 3. Answer is 3: replace 'h' with 'r', delete 'r', delete 'e'.

Flavor 3 — Unique Paths / Min Path Sum (LC 62, 64)

Robot at top-left of an m × n grid, can only move right or down. Count paths to bottom-right, or minimize the sum of cell values along the path.

def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]


def min_path_sum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[m - 1][n - 1]

Worked example for unique paths on a 3×3 grid. The first row and column are all 1 (only one way to walk along an edge). Each interior cell sums up and left:

dp[1][1] = 1 + 1 = 2, dp[2][2] = 3 + 3 = 6. Six unique paths, which matches the closed form C(m+n-2, m-1) = C(4, 2) = 6.

Flavor 4 — Longest Palindromic Subsequence / expand-around-center (LC 5, 516)

Two distinct subproblems sharing the palindrome flavor. LC 516 asks for the longest palindromic subsequence — a 2D DP over substring ranges. LC 5 asks for the longest palindromic substring — solvable with the same DP, but the O(n²) expand-around-center trick is simpler and uses O(1) extra space.

def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = (dp[i + 1][j - 1] if length > 2 else 0) + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]


def longest_palindromic_substring(s: str) -> str:
    def expand(l: int, r: int) -> tuple[int, int]:
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1
    best_l, best_r = 0, 0
    for i in range(len(s)):
        l1, r1 = expand(i, i)        # odd-length center
        l2, r2 = expand(i, i + 1)    # even-length center
        if r1 - l1 > best_r - best_l:
            best_l, best_r = l1, r1
        if r2 - l2 > best_r - best_l:
            best_l, best_r = l2, r2
    return s[best_l : best_r + 1]

Worked example. s = "babad". Center expansion at each index:

Both “bab” and “aba” have length 3; either is a valid answer.

Why it works — the invariant

Every cell dp[i][j] solves an independent subproblem: “the answer for prefix s1[..i] versus prefix s2[..j]” or “the best result reaching grid cell (i, j)”. The transition only reads cells with strictly smaller i+j (up, left, or up-left), so once you fill the table in row-major order each cell sees only finished work. There’s no circular dependency, no recomputed subproblem, and no future to look at — the past fully determines the present. That’s why memoised recursion and bottom-up iteration give the same answer; the bottom-up version just trades a recursion stack for a clean nested loop.

Complexity

• Time: O(m × n). One unit of work per cell. The string flavors are O(|word1| × |word2|); the grid flavors are O(rows × cols).
• Space: O(m × n) for the full table. Almost every 2D-DP problem here can be reduced to O(min(m, n)) by keeping only the previous row (or previous and current rows) in a rolling buffer — useful when one dimension is huge but the other is small. Do this after the 2D version is correct, never before.

Common pitfalls

• Off-by-one between strings and dp. Strings are 0-indexed, the dp table is usually 1-indexed (so row 0 / col 0 are clean base cases). Inside the loop you compare text1[i - 1] with text2[j - 1]. Forget the - 1 and you get index errors or wrong answers.
• Subsequence vs substring. LCS and longest palindromic subsequence allow gaps; longest palindromic substring and longest common substring don’t. The transition for substring problems resets to 0 on a mismatch instead of taking the max — totally different recurrence.
• Wrong base cases. Edit distance needs dp[i][0] = i and dp[0][j] = j, not zeros. Min path sum needs the first row and column to be prefix sums, not copies. Initialising the wrong base row silently produces an off-by-grid[0][0] answer that passes small tests.
• Optimising space too early. The rolling-row trick reads dp[i-1][j] and dp[i-1][j-1] from the previous row, but dp[i][j-1] from the current row. Get the read order wrong and you overwrite a value before using it. Always get the 2D version green first, then collapse.
• Iteration order on range DP. Longest palindromic subsequence fills by substring length, not by (i, j) row-major — because dp[i][j] depends on dp[i+1][j-1], a shorter range. If you naively loop i then j upward you’ll read uninitialised cells.

Where you see this in production

This pattern is the engine behind a surprising amount of infrastructure:

• diff / git diff / patch. GNU diff and most modern diff engines compute the longest common subsequence of two files line by line; the LCS edges are the unchanged lines, everything else is an insert or delete. Myers’ diff algorithm is an optimised LCS that runs in O((m+n)·D) where D is the edit distance, but the underlying problem is exactly LC 1143.
• wdiff and review tooling. Word-level diffs (GitHub’s “word diff”, git diff --word-diff, wdiff) run LCS over tokens instead of lines — same algorithm, finer granularity.
• Levenshtein-based fuzzy matching in Elasticsearch. The fuzzy query and match with fuzziness: AUTO use bounded edit distance (LC 72 with an early-exit cutoff) to score “did you mean” suggestions and tolerate typos in user queries.
• Mobile-keyboard autocorrect. iOS and GBoard score candidate words by edit distance from the typed string, weighted by key adjacency on the soft keyboard. The core scoring loop is the same DP table you just filled for “horse” → “ros”.
• DNA sequence alignment (Smith-Waterman, used in BLAST). Local alignment of two genetic sequences is edit distance with custom scoring — match bonus, mismatch penalty, gap penalty — over the same 2D table. BLAST seeds with exact matches, then runs Smith-Waterman locally to extend the alignment.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• Striver / Take U Forward — DP playlist — www.youtube.com