Dynamic Programming II: Grids & Strings

Some problems need more than one coordinate to describe the state. In grid DP, you need a row and a column. In string DP, you often need positions in two strings. In knapsack, you need which items are available and how much capacity remains.

The move from 1-D to 2-D does not change the discipline: define the state, write the recurrence, set the base cases, and fill in an order that respects the dependencies. The table is bigger, but the thinking is the same.

String DP deserves special attention because many hard-looking interview problems are just prefix comparisons: “best answer using the first i characters of one string and the first j characters of another.”

The mental model

A 2-D state usually means one of these:

• dp[r][c] — answer for a grid cell.
• dp[i][j] — answer for prefixes text1[:i] and text2[:j].
• dp[i][cap] — answer using the first i items with capacity cap.

For grid paths that only move down or right, each cell depends on the cell above and the cell to the left:

for r in range(rows):
    for c in range(cols):
        dp[r][c] = ways_from_top + ways_from_left

For two-string prefix DP, the extra zero row and zero column make base cases clean. They represent comparing against an empty prefix:

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] = 1 + dp[i - 1][j - 1]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

The fill order is not decorative. If a cell reads top, left, and diagonal, you must fill rows left-to-right, top-to-bottom or use an equivalent order where those values already exist.

Pattern recognition

Variations

Worked problems

Try each yourself before revealing the solution. Pay attention to what each table cell means before reading the code.

def unique_paths(m, n):
    row = [1] * n

    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]

    return row[-1]

def longest_common_subsequence(text1, text2):
    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] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    prev = list(range(n + 1))

    for i in range(1, m + 1):
        curr = [i] + [0] * n

        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                delete = prev[j]
                insert = curr[j - 1]
                replace = prev[j - 1]
                curr[j] = 1 + min(delete, insert, replace)

        prev = curr

    return prev[n]

The fill-order pitfall

When a prompt compares two prefixes, imagine the table before you code. Label the empty row and column, say what a diagonal move means, and only then choose whether the final implementation needs the whole table or just a rolling row.