2-D DP on grids and strings

When one index is not enough

In 1-D DP, one number (a position or an amount) described each smaller problem. Some problems need two. "How many ways can I reach cell (r, c)?" needs a row and a column. "How alike are the first i letters of one word and the first j letters of another?" needs i and j. The table becomes a grid, dp[i][j], and the four-step recipe stays the same.

Unique paths in a grid, with obstacles

A robot starts at the top-left cell and may only move right or down. Some cells are blocked (marked 1). How many different paths reach the bottom-right cell? State: dp[r][c] = the number of paths from the start to cell (r, c). The last move into (r, c) came from above or from the left, so dp[r][c] = dp[r − 1][c] + dp[r][c − 1], and a blocked cell has dp = 0. Base case: dp[0][0] = 1 if the start is free. Fill row by row, left to right, so the cells above and to the left are always ready.

Each row only reads the row above it, so one list of length n is enough: dp[c] still holds the value from the row above until you overwrite it, and dp[c − 1] already holds the new value from the left. Time O(m × n), space O(n).

Minimum path sum

Same moves, but each cell has a cost and you want the cheapest path. dp[r][c] = grid[r][c] + min(dp[r − 1][c], dp[r][c − 1]). The first row can only be reached from the left and the first column only from above, so fill those as running sums first. For [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7, along 1 → 3 → 1 → 1 → 1.

Longest common subsequence (LCS)

A subsequence keeps some characters of a string in their original order, not necessarily next to each other: "ace" is a subsequence of "abcde", "aec" is not. The LCS of two strings is the longest string that is a subsequence of both. State: dp[i][j] = the LCS length of the first i characters of a and the first j characters of b. If a[i − 1] == b[j − 1], that character can end the common subsequence: dp[i][j] = dp[i − 1][j − 1] + 1. Otherwise one of the two last characters is not used: dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]). Row 0 and column 0 are 0 (an empty string has nothing in common).

The table above is for a = "abcde" (rows) and b = "ace" (columns). The answer, 3, is in the bottom-right cell.

Rebuilding the answer from the table

The table stores lengths, not the string, but you can walk back from the bottom-right cell. If the two characters match, that character is in the LCS: take it and move diagonally up-left. Otherwise move to whichever neighbour (up or left) holds the larger value. Collect characters in a list and reverse it at the end. The same walk-back idea rebuilds paths in grids and the list of edits in edit distance.

def lcs_string(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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])
    out, i, j = [], m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))

print(lcs_string("abcde", "ace"))   # Output: ace

Edit distance

The edit distance (Levenshtein distance) between two words is the fewest single-character edits (insert, delete or replace) that turn one into the other. "horse" becomes "ros" in 3 edits: replace h with r, delete r, delete e. State: dp[i][j] = the edits to turn the first i characters of a into the first j characters of b. Base cases: dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything). If the last characters match, dp[i][j] = dp[i − 1][j − 1]. Otherwise 1 + the smallest of: dp[i − 1][j] (delete from a), dp[i][j − 1] (insert into a) and dp[i − 1][j − 1] (replace). Time O(m × n); two rows give O(n) space when you only need the number.

Common mistakes

• Building the grid with [[0] * n] * m, which makes every row the same list. Fix: [[0] * n for _ in range(m)].
• Forgetting the extra row and column for the empty prefix in string DP, then reading dp[−1] by accident. Fix: make the table (m + 1) × (n + 1) and use a[i − 1] for the i-th character.
• In unique paths, setting the whole first row to 1 even after an obstacle. Fix: once a cell in the first row or column is blocked, every cell after it in that row or column is 0; the general rule handles it if you start from dp[0][0].
• Confusing subsequence with substring. A substring must be continuous; LCS allows gaps. Fix: read the question and test "abcde" with "ace".
• Mixing up insert and delete in edit distance. Both cost 1, so the number is the same, but the walk-back changes. Fix: write what each neighbour means as a comment.