2D DP & Grid Problems

10⁵⁸ routes, 10,000 cells

A robot stands in the top-left cell of a 100 × 100 grid. Every cell has a cost, and the robot may only step right or down. What is the cheapest route to the bottom-right corner?

The obvious plan tries every route. A route is 99 steps down and 99 steps right in some order, so there are C(198, 99) ≈ 2.3 × 10⁵⁸ of them. No computer will finish that.

Yet the grid has only 10,000 cells. The slow plan keeps asking the same question, what is the cheapest way to reach this cell?, once for every route that passes through it. Answer it once per cell, in an order where each answer is ready before a neighbour needs it, and 10⁵⁸ routes shrink to 10,000 small updates.

That is the whole lesson: name each subproblem by two coordinates (a cell of a grid, or how much of each of two strings you have used), store one answer per pair, and fill the table in an order where every cell's inputs are already there.

Prerequisites. This lesson builds on Dynamic Programming Mastery, which covers what makes a problem DP, memoization versus tabulation, and rebuilding an answer from a table; here those ideas get a second coordinate. 1D DP Problems has Coin Change, whose reuse-allowed loop comes back in Move 7 as the bug to avoid. From Foundation: Arrays & Strings you need two habits: a subsequence may skip elements while a subarray may not, and you read the output contract before you overwrite an input.

Three sentences before any code

Every table in this lesson is designed by answering three questions, in writing, before the first loop:

1. What does dp[i][j] mean? A full sentence: what value, for which subproblem. "The number of routes from (0, 0) to (i, j)" is a definition. "The answer for i and j" is not.
2. Which cells does it read? Draw an arrow from each input cell to dp[i][j]. The arrows decide the fill order (Move 3) and how much you must keep (Move 4).
3. Which cells need no inputs, and where is the answer? Those are the base cases, and the answer is not always the bottom-right corner.

Watch one detail in question 1. In a grid, i and j name a cell. In the string problems of Moves 5 and 6 they are lengths: dp[i][j] describes the first i characters of one string and the first j of the other. That is why those tables need an extra row and column for the empty prefix. Grid tables do not need one, though Move 2 shows when adding one anyway pays off.

Move 1: Count routes, one cell at a time

Smell: routes that only move right or down, and a question about all of them: how many, or which is best.

How many ways to get here?

A robot on an m × n grid starts at the top-left and moves only right or down. How many different routes reach the bottom-right corner? This is LeetCode 62: Unique Paths. Coordinates are (row, column), zero-based.

The slow version follows the definition. The routes into (i, j) come from the cell above or the cell to the left, so ask both:

def count_paths_slow(m, n):
    def paths(i, j):                       # routes from (0, 0) to (i, j)
        if i == 0 or j == 0:
            return 1                       # a straight line along an edge
        return paths(i - 1, j) + paths(i, j - 1)
    return paths(m - 1, n - 1)

Predict first: on a 4 × 4 grid, count_paths_slow(4, 4) starts at paths(3, 3). How many times does it evaluate paths(1, 1)?

The slow version repeats the question "how many routes reach (i, j)?" So answer it once per cell and store it:

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 or j == 0:
                dp[i][j] = 1                            # a straight line along an edge
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]  # from above + from the left
    return dp[m - 1][n - 1]

The table for a 3 × 4 grid, printed by filling it with this loop:

unique_paths(3, 4) returns 10, and unique_paths(3, 7) returns 28, LeetCode's first example. The cost is one addition per cell: O(m·n) time and O(m·n) extra space for the table. Move 4 cuts the space to one row.

Why adding is right

Every route into (i, j) takes its last step either from above or from the left. No route does both, so the two groups do not overlap, and together they contain every route. The count is therefore the sum of the two counts. The edge cells get 1 because the only way to reach a cell in row 0 is to step right every time.

The loop keeps one promise: when it reaches (i, j), every cell above it and to its left already holds its final count. Rows go top to bottom and each row goes left to right, so both parents are always finished.

🧠 A free test oracle. A route is m − 1 downs and n − 1 rights in some order, so there are C(m + n − 2, m − 1) of them: math.comb(m + n - 2, m - 1). Use it to check the table on small inputs. The formula stops working the moment a cell is blocked or has a cost; the table keeps working.

⚠️ Overflow outside Python. Python integers never overflow. In Java or C++, LeetCode 62 promises an answer of at most 2 × 10⁹, which fits a 32-bit signed int, and no cell of the table is larger than the corner, so the table is safe. Computing C(m + n − 2, m − 1) through factorials overflows long before that.

Blocked cells

LeetCode 63: Unique Paths II adds obstacles: grid[i][j] == 1 is blocked. A route cannot end on a blocked cell, so its count is 0, and it passes 0 to its neighbours. With guards for the missing parents, one loop handles every cell, including the edges:

def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[i][j] = 0                   # blocked: no route ends here
            elif i == 0 and j == 0:
                dp[i][j] = 1                   # the start
            else:
                top = dp[i - 1][j] if i > 0 else 0
                left = dp[i][j - 1] if j > 0 else 0
                dp[i][j] = top + left
    return dp[m - 1][n - 1]

A blocked start or a blocked corner needs no special case: the start gets 0, and a blocked corner is 0 by the first branch.

⚠️ The classic bug keeps Unique Paths' shortcut: fill row 0 and column 0 with 1s, then run the main loop from (1, 1). An obstacle in row 0 cuts off every cell to its right, because walking along row 0 is the only way to reach them. Those cells must be 0, not 1.

Your turn: predict the table for this grid, then the answer. Which row-0 cells are 0, and why? What does the "edges are all 1" version return?

0 1 0 0
0 0 0 0
0 0 1 0

Move 2: The cheapest route: swap + for min

Smell: the same right/down moves, but each cell has a cost and you want the cheapest route, not the number of routes.

The greedy robot

LeetCode 64: Minimum Path Sum gives a grid of non-negative costs. A route pays for every cell it visits, including the first and the last.

Predict first: on this grid, a robot always steps to the cheaper of its two options. What does it pay? Is that the minimum?

1 3 1
1 5 1
4 2 1

The table stores, for every cell, the cheapest total of any route that ends there. The recurrence is Move 1's with min in place of +, plus the cell's own cost:

def min_path_table(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[i][j] = grid[0][0]
            elif i == 0:
                dp[i][j] = grid[i][j] + dp[i][j - 1]    # top row: only from the left
            elif j == 0:
                dp[i][j] = grid[i][j] + dp[i - 1][j]    # left column: only from above
            else:
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp

def min_path_sum(grid):
    return min_path_table(grid)[-1][-1]

The table for the grid above:

Look at (1, 1): its own cost is 5, the route total above it is 4 and the one to its left is 2, so it holds 5 + 2 = 7. The corner holds 7. O(m·n) time, O(m·n) extra space.

Why the minimum is safe

The cheapest route to (i, j) arrives from above or from the left. Everything before that last step is a route to the neighbour, and it must be the cheapest route to that neighbour: if a cheaper one existed, you could paste it in and make the whole route cheaper. So the best total at (i, j) is its own cost plus the smaller of the two neighbours' best totals. This is optimal substructure, argued by cut and paste, and every min or max table in this lesson rests on a version of it.

The argument never used "costs are non-negative". Right/down routes never revisit a cell, so negative costs are fine here too. Keep that in mind for Move 3, where the robot can walk back: then no fill order exists, and negative costs are no longer safe.

⚠️ The one-character bug. Writing min(grid[i - 1][j], grid[i][j - 1]) compares the two neighbours' own costs instead of the route totals that end there. That is the greedy robot again, and it fails even on a 2 × 2 grid: [[3, 1], [1, 3]] gives 4 instead of 7, because it forgets that every route also paid for the start.

Walk back to recover the route

The table stores totals, not decisions, but the decisions can be recovered. At any cell, the best route came from whichever parent has the smaller total. Start at the corner and walk back:

def cheapest_route(grid):
    dp = min_path_table(grid)
    i, j = len(grid) - 1, len(grid[0]) - 1
    route = [(i, j)]
    while (i, j) != (0, 0):
        if j == 0 or (i > 0 and dp[i - 1][j] <= dp[i][j - 1]):
            i -= 1                          # the best route arrived from above
        else:
            j -= 1                          # ... or from the left
        route.append((i, j))
    return route[::-1]

On the grid above it returns [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)], whose costs 1, 3, 1, 1, 1 add to 7. The walk takes O(m + n) steps after the table is built. It needs the whole table, which matters in Move 4.

Top-down, and its limit

The same recurrence as memoized recursion reads almost like the definition:

from functools import cache

def min_path_sum_memo(grid):
    @cache
    def best(i, j):                          # cheapest route from (0, 0) to (i, j)
        if i == 0 and j == 0:
            return grid[0][0]
        options = []
        if i > 0:
            options.append(best(i - 1, j))
        if j > 0:
            options.append(best(i, j - 1))
        return grid[i][j] + min(options)
    return best(len(grid) - 1, len(grid[0]) - 1)

It is correct, but the recursion goes about m + n − 1 calls deep before it reaches the start. CPython's default limit is 1,000 frames. LeetCode 64 caps the grid at 200 × 200 (depth 399), which is fine; a 500 × 500 grid raises RecursionError. You can raise the limit with sys.setrecursionlimit, but the loop version has no depth at all. Advanced Recursion & Backtracking covers recursion limits in general.

Sentinels instead of edge cases

The three if branches for the start, the top row and the left column can be replaced by padding: one extra row and column filled with a value that can never win. For min, that value is infinity. One seed cell makes the start come out right:

def min_path_sum_padded(grid):
    m, n = len(grid), len(grid[0])
    INF = float('inf')
    dp = [[INF] * (n + 1) for _ in range(m + 1)]
    dp[0][1] = 0              # seed: the start cell computes grid[0][0] + min(INF, 0)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = grid[i - 1][j - 1] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

For the grid [[1, 3], [2, 4]] the padded table is [[∞, 0, ∞], [∞, 1, 4], [∞, 3, 7]], and the answer is 7. Forget the seed and every cell is ∞, because the start adds its cost to min(∞, ∞). The padding costs O(m + n) extra cells, the same complexity class. Watch the index shift: table cell (i, j) is grid cell (i − 1, j − 1). You will meet this trick again in Move 3. Move 5's extra row looks the same but is not padding: it holds a real subproblem, the empty prefix.

Your turn: fill the table for [[1, 2, 3], [4, 5, 6]] and walk back to the route. Then suppose grid[1][1] became −5. Does the recurrence still give the right answer?

Move 3: Let the arrows choose the order

Smell: your recurrence reads a cell that your loop has not filled yet.

Draw an arrow from every input cell to the cell that reads it. Any fill order in which every arrow points from an earlier cell to a later one works. Row by row, left to right satisfies arrows from above, from the left and from the upper-left, which covers Moves 1, 2, 5 and 6. Other problems point their arrows elsewhere:

The knight who cannot plan forward

LeetCode 174: Dungeon Game. A knight starts in the top-left room and must reach the bottom-right room, moving right or down. Each room changes his health: negative numbers are demons, positive numbers are potions. His health must stay at least 1 at every moment, including right after the first and the last room. What is the smallest starting health that works?

Predict first: try to run it forward. For each room, store the smallest starting health that gets the knight there alive. On the grid below, two routes reach room (1, 2): route A goes down, right, right (rooms 1, 0, −2, 0) and route B goes right, right, down (rooms 1, −3, 3, 0). Which one should the forward table keep for (1, 2), and what does that choice do to the final answer?

 1  -3   3
 0  -2   0
-3  -3  -3

Now flip the direction. Let need[i][j] be the smallest health the knight can walk into room (i, j) with and still reach the princess. From a room onward, the past no longer matters; only the rest of the route does, and one number describes it. After this room he continues right or down, whichever needs less, call that after. Walking in with h health, he leaves with h + dungeon[i][j], which must be at least after. And h itself must be at least 1. So:

need[i][j] = max(1, after − dungeon[i][j])

The cells this reads are below and to the right, so the loops run backward. Padding with ∞ (Move 2's sentinel trick) handles the bottom row and right column, and two seeds of 1 say "after the last room, 1 health is enough":

def min_health(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    INF = float('inf')
    need = [[INF] * (n + 1) for _ in range(m + 1)]   # padding: row m, column n
    need[m][n - 1] = need[m - 1][n] = 1              # seeds: after the last room, 1 HP is enough
    for i in range(m - 1, -1, -1):                   # bottom row first
        for j in range(n - 1, -1, -1):               # right to left
            after = min(need[i + 1][j], need[i][j + 1])   # cheaper way onward
            need[i][j] = max(1, after - dungeon[i][j])
    return need[0][0]

The table for the grid above, as the loop fills it (padding not shown):

The answer is need[0][0] = 3. Read the corner first: the knight must enter the −3 room with 4 to leave with 1. Room (0, 2) holds a potion of 3, so walking in with 1 is enough (1 + 3 = 4). The max(1, …) matters after a big potion: without it, a +10 room followed by a room that needs 1 would claim the knight could walk in with −9 health. On LeetCode's example, [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]], the function returns 7. O(m·n) time and space.

🧠 When one number per cell cannot summarise the past, you have two ways out. Flip the direction so each cell summarises the future, as here. Or store more per cell: a right/down route that maximises a product of possibly negative numbers needs both the largest and the smallest product at each cell, because a very negative product times a negative cell value becomes the largest.

Order by value: Longest Increasing Path

LeetCode 329: Longest Increasing Path in a Matrix allows moves in all four directions, but only to a strictly larger value. A cell's answer reads its larger neighbours, and values strictly increase along every step, so the arrows can never loop. Process the cells from the largest value down, and each cell's inputs are done:

def longest_increasing_path(matrix):
    m, n = len(matrix), len(matrix[0])
    longest = [[1] * n for _ in range(m)]
    cells = sorted(((matrix[i][j], i, j) for i in range(m) for j in range(n)), reverse=True)
    for value, i, j in cells:                 # largest values first
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            a, b = i + di, j + dj
            if 0 <= a < m and 0 <= b < n and matrix[a][b] > value:
                longest[i][j] = max(longest[i][j], 1 + longest[a][b])
    return max(max(row) for row in longest)

It returns 4 for LeetCode's [[9, 9, 4], [6, 6, 8], [2, 1, 1]] (the path 1, 2, 6, 9). Sorting costs O(mn log(mn)) time; the updates cost O(mn). A memoized DFS gives the same answers, but on a 200 × 200 grid an increasing path can cover all 40,000 cells. Put walls of small values between the rows of a snake and the DFS has no shortcut: it follows a path of about 20,000 cells one call at a time and raises RecursionError in Python. The sorted loop has no recursion.

When no order exists

Give the Minimum Path Sum robot the freedom to step up and left as well. Now a cell's cheapest route may arrive from the cell below it, and the cheapest route to that cell may pass through the first one: the arrows form cycles, and no fill order can finish every input first. It is not a table problem any more. It is a shortest-path problem on a graph, solved with Dijkstra's algorithm, which Shortest Path Algorithms teaches. The difference is real:

1 1 1
9 9 1
1 1 1
1 9 9
1 1 1

The right/down table gives 15: along the top, then straight down the right column through a 9. Allowed to move freely, the robot snakes right, down, left, down, right through the 1s and pays 11.

Your turn: pick the loop order. LeetCode 516: Longest Palindromic Subsequence uses dp[i][j] = the longest palindromic subsequence inside s[i..j], with dp[i][i] = 1 and:

• if s[i] == s[j]: dp[i][j] = dp[i + 1][j − 1] + 2
• otherwise: dp[i][j] = max(dp[i + 1][j], dp[i][j − 1])

In which order must i and j run? What does "bbbab" give?

def lps(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):        # shorter ranges (larger i) first
        dp[i][i] = 1
        for j in range(i + 1, n):         # dp[i][j - 1] is already done on this row
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1] if n else 0

Move 4: Keep one row

Smell: row i reads only row i − 1 and cells to its left in row i. Everything older is dead weight.

Rolling the table changes memory, never time. A 10,000 × 10,000 table has 10⁸ cells; a Python list of lists stores an 8-byte reference per cell, so it needs at least 800 MB before counting the integers themselves. One row is 10,000 references, about 80 KB. Rolling turns Memory Limit Exceeded into Accepted; it cannot fix Time Limit Exceeded, because every cell is still computed. On LeetCode the full table usually fits (Minimum Path Sum's largest table is 40,000 cells), so rolling is most often an interview follow-up. Triangle and Interleaving String ask for it explicitly.

Two rows, then one

The direct version keeps the previous row and builds the current one:

def min_path_sum_rows(grid):
    m, n = len(grid), len(grid[0])
    prev = [0] * n
    for i in range(m):
        curr = [0] * n
        for j in range(n):
            if i == 0 and j == 0:
                curr[j] = grid[0][0]
            elif i == 0:
                curr[j] = grid[i][j] + curr[j - 1]
            elif j == 0:
                curr[j] = grid[i][j] + prev[j]
            else:
                curr[j] = grid[i][j] + min(prev[j], curr[j - 1])
        prev = curr                        # the finished row becomes "the row above"
    return prev[-1]

Look at what curr[j] reads: prev[j], which is directly above, and curr[j − 1], which was just written. Nothing else. So one array can play both parts:

def min_path_sum_1d(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[j] = grid[0][0]
            elif i == 0:
                dp[j] = grid[i][j] + dp[j - 1]          # left only
            elif j == 0:
                dp[j] = grid[i][j] + dp[j]              # above only
            else:
                dp[j] = grid[i][j] + min(dp[j], dp[j - 1])  # dp[j] = above, dp[j-1] = left
    return dp[-1]

Why one array works. Just before the loop writes position j of row i, the array is split: dp[:j] already holds row i, and dp[j:] still holds row i − 1. So dp[j] is the cell above and dp[j − 1] is the cell to the left, exactly the two inputs. Writing dp[j] moves the split one step right.

On the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the array after each row is [1, 4, 5], then [2, 7, 6], then [6, 8, 7]: the rows of Move 2's table, one at a time. Here is the split in the middle of the last row, marked |:

after row 1:                 dp = [ 2, 7, 6 ]
row 2, just before j = 1:    dp = [ 6 | 7, 6 ]
                                    ^   ^
                  left, already row 2   above, still row 1
row 2, j = 1 writes 2 + min(7, 6) = 8

Same O(m·n) time; extra space drops from O(m·n) to O(n).

Two ways to break it

⚠️ Direction. Run the inner loop right to left and dp[j − 1] has not been written yet on this pass. In row 0 it is still the initial 0; in later rows it is the stale value from the row above, the cell diagonally above-left. The robot can no longer step right at all: its left move is replaced by a diagonal jump. On the grid above the function silently returns 3 instead of 7.

⚠️ The first column. Drop the j == 0 branch and let the general formula handle j = 0. It reads dp[-1], and Python treats that as the last element: the end of the previous row. No error is raised, and the robot can now teleport from the end of one row to the start of the next. On the 3 × 3 grid above this still returns 7, so a small test passes. The tall grid [[1, 1], [9, 1], [1, 9], [1, 1]] exposes it: 6 instead of 13. Guard j == 0 explicitly, and test tall, narrow grids as well as square ones.

What rolling costs you

• The route. Move 2's walk back needs the whole table. Keep the table if you must return the route itself, not only its cost.
• Choice of dimension. Roll along the shorter side. For a right/down grid, transposing it gives the same routes with the same sums, so you can keep a row of length min(m, n): O(min(m, n)) space.
• In place. Writing the totals into grid itself uses O(1) extra space but destroys the input. Do it only when the contract allows it.

Your turn: roll Unique Paths to one row. Predict the row after each pass for m = 3, n = 4.

def unique_paths_row(m, n):
    row = [1] * n                         # row 0: one route to each cell
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]          # old row[j] = above, row[j-1] = left (already new)
    return row[-1]

Move 5: Two strings, one table: Longest Common Subsequence

Smell: two sequences, and the question is how well they line up. Brute force tries all 2ᵐ subsequences of one string.

LeetCode 1143: Longest Common Subsequence asks for the length of the longest string that is a subsequence of both inputs. For "abcde" and "ace" it is 3 ("ace"). A subsequence keeps order but may skip characters, so "ace" counts even though its letters are not adjacent in "abcde".

Predict first: a quick scan walks through text1 and matches each character to its first unused occurrence in text2, moving forward only. What does it find for text1 = "zabc" and text2 = "abcz"? What is the true LCS?

Prefix pairs

Define dp[i][j] = the LCS length of text1[:i] and text2[:j], the first i and first j characters. Here i and j are lengths, so they run from 0 to m and 0 to n. Row 0 and column 0 are the empty prefixes, which have LCS 0 with anything. They are real subproblems, not padding, and they remove every edge case. The characters that cell (i, j) compares are text1[i − 1] and text2[j − 1].

def lcs_table(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]   # row 0 and column 0: empty prefixes
    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              # use the matching pair
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop one last character
    return dp

The table for text1 = "abcde" (rows) and text2 = "ace" (columns):

Each number jumps only at a match: row c, column c takes the diagonal 1 and adds 1. The answer is the corner, 3. O(m·n) time and space.

Why two cases are enough

Look at the last characters of the two prefixes.

• They are equal. Some LCS uses both of them as a pair. Take any LCS. If it uses neither, add the pair to its end: longer, which is impossible. If it uses only one of them, say text1's last character paired with an earlier copy in text2, re-pair it with text2's last character instead: same length. So dp[i][j] = dp[i − 1][j − 1] + 1.
• They differ. They cannot pair with each other. They cannot both be used either: each would be paired with something earlier in the other string, and those two pairs would cross, breaking order. So at least one of them is unused. Drop it and keep the better result: max(dp[i − 1][j], dp[i][j − 1]).

Walk back to the string

Walk back from the corner, as in Move 2. A match was used by the table, so take it and move diagonally. Otherwise move towards whichever neighbour keeps the larger value:

def lcs_string(text1, text2):
    dp = lcs_table(text1, text2)
    i, j = len(text1), len(text2)
    out = []
    while i > 0 and j > 0:
        if text1[i - 1] == text2[j - 1]:
            out.append(text1[i - 1])            # this pair is in the answer
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1                               # dropping text1[i-1] loses nothing
        else:
            j -= 1
    return "".join(reversed(out))

lcs_string("abcde", "ace") returns "ace". If you only need the length, roll the table to one row as in Move 4, along the shorter string, for O(min(m, n)) space. The diagonal needs one saved variable, shown in Move 6.

⚠️ Subsequence or substring? For the longest common substring (contiguous), dp[i][j] must mean "the common run that ends at these two characters". A mismatch then resets it to 0, and the answer is the largest cell anywhere, not the corner. The final round has this one.

Your turn: LeetCode 583: Delete Operation for Two Strings asks for the minimum number of deletions, from either string, that make the two strings equal. How does the LCS give it? Compute it for "sea" / "eat" and "leetcode" / "etco".

def min_deletions(word1, word2):
    common = lcs_table(word1, word2)[-1][-1]
    return len(word1) + len(word2) - 2 * common

Move 6: Edit Distance: three neighbours, three operations

Smell: turn one string into another and count the operations.

LeetCode 72: Edit Distance allows three operations on word1, each costing 1: insert a character, delete a character, replace a character. The minimum for "horse" → "ros" is 3.

Predict first: what is the edit distance from "abc" to "bca"? Every position differs, so is it 3 replacements?

State, base cases, and three neighbours

dp[i][j] = the minimum operations to turn word1[:i] into word2[:j]. The empty prefixes give the base cases: dp[i][0] = i (delete all i characters) and dp[0][j] = j (insert all j). Each of the three neighbours of dp[i][j] stands for one operation:

• From dp[i − 1][j]: you already turned word1[:i − 1] into word2[:j], so delete word1[i − 1].
• From dp[i][j − 1]: you turned word1[:i] into word2[:j − 1], so insert word2[j − 1] at the end.
• From dp[i − 1][j − 1]: the two last characters are aligned with each other: free if they are equal, one replace if not.

def edit_table(word1, word2):
    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 all i characters
    for j in range(n + 1):
        dp[0][j] = j                       # insert all j characters
    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]           # last characters already agree
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # delete word1[i-1]
                                   dp[i][j - 1],      # insert word2[j-1]
                                   dp[i - 1][j - 1])  # replace word1[i-1] by word2[j-1]
    return dp

The table for "horse" (rows) → "ros" (columns):

Row h, column r is 1: replace h by r. Row o, column o copies the diagonal 1 for free. The corner is 3. Walking back from it the way Move 2 did (follow whichever neighbour produced the value) gives replace 'h' with 'r', delete 'r', delete 'e', the same script as LeetCode's explanation. O(m·n) time and space.

Why the recurrence is complete, and why a match is free

In an optimal edit, look at what happens to the last characters. Either word1's last character is deleted, or word2's last character was inserted, or the two are aligned with each other. Those three cases cover every edit sequence, and each leaves a smaller prefix pair, so the minimum over the three neighbours is exact.

When the last characters are equal, the code skips the two + 1 options. That is safe: adding one character to either string changes the distance by at most 1, so dp[i − 1][j] + 1 and dp[i][j − 1] + 1 are never smaller than dp[i − 1][j − 1]. The free diagonal always wins.

LCS is edit distance without replace. With only inserts and deletes, a mismatched pair costs 2 (delete one, insert the other) and the distance is m + n − 2 · LCS, exactly the exercise in Move 5. Replace makes a mismatched pair cost 1.

Where this shows up outside LeetCode: spell-checkers use it to rank candidate corrections; DNA alignment uses the same table with scores instead of unit costs (Needleman–Wunsch for whole sequences, Smith–Waterman for the best matching region); and diff computes a shortest insert/delete script between two files' lines, the LCS problem, with faster specialised algorithms.

Your turn: roll edit_table to a single row, as in Move 4. Which old value do you lose before you need it, and how do you keep it?

def edit_distance(word1, word2):
    n = len(word2)
    row = list(range(n + 1))                 # row 0: j insertions
    for i in range(1, len(word1) + 1):
        diag = row[0]                        # dp[i-1][0], about to be overwritten
        row[0] = i
        for j in range(1, n + 1):
            above = row[j]                   # dp[i-1][j], also next j's diagonal
            if word1[i - 1] == word2[j - 1]:
                row[j] = diag
            else:
                row[j] = 1 + min(above, row[j - 1], diag)
            diag = above
    return row[n]

Move 7: Items and a budget: 0/1 knapsack

Smell: choose a subset of items, each at most once, under a limit on total weight (or cost, or size), to maximise value or to hit an exact target.

Predict first: a bag holds 50 kg. Items: 10 kg worth 60, 20 kg worth 100, 30 kg worth 120. Take items in order of value per kilogram (6, 5, 4). What do you get? Is it the best?

Item × capacity

dp[i][c] = the best value using only the first i items with capacity c. Item i − 1 is either skipped (dp[i − 1][c]) or taken once, if it fits (dp[i − 1][c − w] + v). Both options read only row i − 1, and that detail matters in a moment.

def knapsack_table(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]    # row 0: no items, value 0
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]                        # skip item i-1
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)   # take it (once)
    return dp

With weights [1, 3, 4], values [15, 20, 30] and capacity 4:

At capacity 4 the second row takes the 3 kg item on top of the best 1 kg packing: 20 + 15 = 35. The third item alone is worth only 30, so the answer stays 35. Why it works is Move 2's cut-and-paste again: if the best packing takes item i − 1, the rest must be the best packing of earlier items in c − w.

Roll it, and loop backward

Row i reads row i − 1 at c and at c − w, which is to the left. Rolled into one array, you must not overwrite the left part before reading it. So the capacity loop runs from high to low:

def knapsack(weights, values, capacity):
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # high to low: best[c - w] is still last row's
            best[c] = max(best[c], best[c - w] + v)
    return best[capacity]

⚠️ Loop upward and the item is reused. Going low to high, best[c − w] may already include the current item, so taking it again stacks a second copy. One item of 1 kg worth 10 with capacity 3: the upward loop returns 30 (three copies), the backward loop returns 10. The upward loop is exactly right when items are unlimited, the Coin Change situation in 1D DP Problems, where each coin may be used again. Direction encodes "once" versus "any number of times".

Yes/no and counting versions

LeetCode 416: Partition Equal Subset Sum asks whether the numbers can be split into two groups with equal sums. That means finding a subset that sums to half the total. The values are weights, and the question is reachability, so the table holds booleans. DP answers yes/no questions as naturally as min, max and count ones:

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False                      # an odd total cannot split evenly
    target = total // 2
    can = [False] * (target + 1)
    can[0] = True                         # the empty subset
    for x in nums:
        for s in range(target, x - 1, -1):
            if can[s - x]:
                can[s] = True
    return can[target]

To count the subsets that reach each sum instead, store integers: ways[0] = 1 and ways[s] += ways[s - x], with the same backward loop.

Cost. O(n · W) time and O(W) extra space, where n is the number of items and W is the capacity (here the target). W is a number in the input, not a count of items, so this is called pseudo-polynomial. LeetCode 416 has at most 200 numbers of at most 100, so the target is at most 10,000 and the loop does at most 2 million updates. With values up to 10⁹ the same table would be hopeless.

Your turn: trace can_partition([1, 5, 11, 5]). List the reachable sums after each number. Then: what does [1, 2, 3, 5] return, and how quickly?

Boss level: two walkers, one clock

LeetCode 741: Cherry Pickup. An n × n grid holds 0 (empty), 1 (a cherry) or −1 (a thorn you cannot enter). Walk from (0, 0) to (n − 1, n − 1) moving right or down, then walk back moving left or up. Every cherry you pass is picked, but each cell's cherry only once. Return the most cherries you can collect, or 0 if there is no valid round trip.

Plot twist: the obvious plan fails

The natural plan: find the best right/down route with Move 2's table (max instead of min), pick its cherries, then find the best route through what is left. Try it here:

0 0 1 0
1 1 1 1
0 0 0 0
0 1 0 0

The best single route takes the whole second row: 4 cherries. The cherries left are at (0, 2) and (3, 1), and no right/down route can reach both, since (3, 1) is left of (0, 2). The second trip adds 1: total 5. But two coordinated trips can split the row: one goes (1, 0), (1, 1), then down to (3, 1); the other goes through (0, 2), (1, 2), (1, 3). Each picks 3, total 6. The first trip's best choice for itself spoiled the second trip. The two trips must be planned together.

One clock for two walkers

The return trip, read backward, is just another right/down route from (0, 0). So send two walkers from the start at the same time, one step each per tick. After t steps each walker satisfies row + column = t. So (t, r1, r2) pins down both positions: the columns are t − r1 and t − r2. Four coordinates (r1, c1, r2, c2) would carry one redundant number; three are enough.

Two walkers stand on the same cell exactly when r1 == r2 at the same t. Could they pick the same cherry at different times? No: a walker can only be on cell (r, c) at step t = r + c. So checking for a collision at each step catches every double count.

from functools import cache

def cherry_pickup(grid):
    n = len(grid)

    @cache
    def best(t, r1, r2):
        # walkers at (r1, t - r1) and (r2, t - r2) after t steps each;
        # returns the most cherries collectable from here to the corner
        c1, c2 = t - r1, t - r2
        if not (0 <= r1 < n and 0 <= c1 < n and 0 <= r2 < n and 0 <= c2 < n):
            return float('-inf')
        if grid[r1][c1] == -1 or grid[r2][c2] == -1:
            return float('-inf')
        here = grid[r1][c1]
        if r1 != r2:                      # same t and same row means same cell
            here += grid[r2][c2]
        if t == 2 * n - 2:                # both stand on the bottom-right corner
            return here
        return here + max(best(t + 1, r1 + d1, r2 + d2)
                          for d1 in (0, 1) for d2 in (0, 1))   # 1 = move down

    return max(0, best(0, 0, 0))

Each of the four (d1, d2) choices moves each walker down (1) or right (0). Blocked or off-grid states return −∞, so they never win a max, and max(0, …) turns "no valid trip at all" into 0. The function returns 6 on the twist grid above, and 5 and 0 on LeetCode's two examples.

Cost. t takes 2n − 1 values and r1, r2 take n each: about 2n³ states with 4 transitions each, so O(n³) time and space. For LeetCode's n ≤ 50 that is 99 × 50 × 50 = 247,500 states. The recursion is only 2n − 1 ≤ 99 calls deep, so memoization is safe here.

💡 The pattern. When two things move through the same grid and interact, give the table a coordinate for each of them. Then look for a shared clock that makes one coordinate redundant.

Final round: no label on the problem

Real problems do not say "2D DP". For each one: write the one-sentence meaning of a cell, draw the arrows, pick the order, and ask whether a table is even the right tool.

Challenge 1: the biggest square

Given a grid of "0" and "1", return the area of the largest square made only of "1"s. This is LeetCode 221: Maximal Square, grids up to 300 × 300.

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Before peeking: what should a cell store? Which cells does it read? Where is the answer?

def maximal_square(matrix):
    m, n = len(matrix), len(matrix[0])
    side = [[0] * n for _ in range(m)]
    best = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == "1":
                if i == 0 or j == 0:
                    side[i][j] = 1
                else:
                    side[i][j] = 1 + min(side[i - 1][j], side[i][j - 1], side[i - 1][j - 1])
                best = max(best, side[i][j])
    return best * best

Challenge 2: a shared run

Given two integer arrays, return the length of the longest contiguous block that appears in both. This is LeetCode 718: Maximum Length of Repeated Subarray, lengths up to 1,000. For [1, 2, 3, 2, 1] and [3, 2, 1, 4, 7] the answer is 3 ([3, 2, 1]). What changes from LCS, and where is the answer?

def find_length(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                best = max(best, dp[i][j])
            # on a mismatch dp[i][j] stays 0: a common run cannot skip
    return best

Challenge 3: the robot that can turn back

The Minimum Path Sum robot may now step up, down, left or right, still paying for every cell it visits, including the start. Grids up to 100 × 100, costs from 1 to 9. Which technique, and why not a table?

Challenge 4: split as evenly as possible

Split a list of positive integers into two groups so the two sums are as close as possible, and return the difference. Up to 30 numbers, each at most 100. For [2, 7, 4, 1, 8, 1] the answer is 1. Which technique? What does the table hold?

def closest_split(stones):
    total = sum(stones)
    half = total // 2
    can = [False] * (half + 1)
    can[0] = True
    for x in stones:
        for s in range(half, x - 1, -1):
            if can[s - x]:
                can[s] = True
    best = max(s for s in range(half + 1) if can[s])
    return total - 2 * best

Cheat sheet

Before moving on, take one problem from this lesson, open a blank editor and explain it aloud: the one-sentence meaning of a cell, which cells it reads and why that is all it needs, the base cases, the fill order that the arrows force, where the answer sits, and what you would lose by rolling it to one row. Then change one rule (allow a move up, let items repeat, make the substring contiguous) and say which part of your design breaks.

Next: when the arrows form cycles, the problem has become a graph. Continue with Graph Algorithms & Search, and see Shortest Path Algorithms for Dijkstra on weighted grids. To revisit the general DP design process, go back to Dynamic Programming Mastery.