2D dynamic programming

The classic table-filling problems. Three of them cover most 2D DP questions: knapsack, longest common subsequence, and edit distance. Learn the shape once and the rest are variations.

The method

Every DP problem answers four questions. Answer them out loud in an interview — it’s more convincing than producing code:

1. What’s the state? What do the indices mean?
2. What’s the recurrence? How does a state depend on smaller ones?
3. What are the base cases?
4. What order do you fill in? Dependencies must already be computed.

0/1 knapsack

Maximise value within a weight capacity; each item used at most once.

def knapsack(weights: list[int], values: list[int], cap: int) -> int:
    n = len(weights)
    # dp[i][w] = best value using the first i items within capacity w
    dp = [[0] * (cap + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(cap + 1):
            dp[i][w] = dp[i - 1][w]                             # skip item i
            if weights[i - 1] <= w:                             # or take it
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][cap]

Space optimisation to 1D is the standard follow-up:

def knapsack_1d(weights, values, cap):
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):
        for w in range(cap, wt - 1, -1):        # BACKWARDS - this is the whole trick
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[cap]

Iterate capacity backwards. Forwards would read dp[w - wt] after it was already updated for this item, letting you use the item more than once — which is exactly the unbounded knapsack. So:

That one-line difference between two problems is a favourite interview detail.

Partition into equal-sum subsets and coin change are knapsack in disguise: subset-sum is knapsack with value = weight, coin change is unbounded knapsack minimising count.

Longest common subsequence

def lcs(a: str, b: str) -> int:
    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      # match: extend the diagonal
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop one character

    return dp[m][n]

dp[i][j] is the LCS length of the first i characters of a and first j of b.

Subsequence, not substring — characters need not be contiguous. Longest common substring is a different recurrence: on a mismatch it resets to 0 rather than taking a max, and the answer is the table maximum rather than the corner.

Variations that are LCS underneath: minimum insertions/deletions to transform one string into another (m + n - 2*lcs), longest palindromic subsequence (lcs(s, reversed(s))), and shortest common supersequence.

Edit distance

def edit_distance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1): dp[i][0] = i          # delete everything
    for j in range(n + 1): dp[0][j] = j          # insert everything

    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]      # free — characters match
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],                # delete from a
                    dp[i][j - 1],                # insert into a
                    dp[i - 1][j - 1],            # substitute
                )

    return dp[m][n]

The three neighbours map to the three operations, and being able to say which is which is the point of the question. Base cases are non-zero here, unlike LCS — transforming a string into the empty string costs one deletion per character.

Grid paths

The simplest 2D DP, and a good warm-up:

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]

Can be done in-place on the grid for O(1) extra space, or with a single row for O(n).

Memoization as the escape hatch

When the recurrence is clear but the fill order isn’t, write it top-down:

from functools import cache

def lcs(a: str, b: str) -> int:
    @cache
    def solve(i: int, j: int) -> int:
        if i == 0 or j == 0:
            return 0
        if a[i - 1] == b[j - 1]:
            return solve(i - 1, j - 1) + 1
        return max(solve(i - 1, j), solve(i, j - 1))

    return solve(len(a), len(b))

Same complexity, and @cache makes it nearly free to write. Write the memoized version first in an interview, confirm it’s correct, then convert to bottom-up if asked about space. Recursion depth is the one risk on large inputs.

Reconstructing the answer

Interviewers often follow up with “now return the actual subsequence”, not just its length. Walk the table backwards:

def lcs_string(a, b, dp):
    i, j, out = len(a), len(b), []
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))

Note this needs the full 2D table, so you can’t have space-optimised to one row. That trade-off — space optimisation versus reconstructability — is worth naming.

Interview angle

• “How do you approach a DP problem?” — define the state, write the recurrence, identify base cases, and determine the fill order. Say those four out loud before writing code; it demonstrates method rather than memorised solutions.
• “Why iterate capacity backwards in 1D knapsack?” — forwards reads an entry already updated for the current item, which permits reusing it. Backwards guarantees each item is considered once. Forwards is exactly how you get unbounded knapsack.
• “Edit distance — what do the three terms mean?” — dp[i-1][j] is deletion, dp[i][j-1] insertion, dp[i-1][j-1] substitution. A character match costs nothing and moves diagonally.
• “LCS versus longest common substring?” — subsequence allows gaps and takes a max on mismatch; substring requires contiguity, resets to zero on mismatch, and the answer is the table maximum rather than the bottom-right corner.
• “Top-down or bottom-up?” — write memoized top-down first: it follows directly from the recurrence and @cache makes it trivial. Convert to bottom-up when you need to avoid recursion depth or optimise space.
• “Now return the actual sequence, not the length.” — walk the completed table backwards, following the choice each cell made. This requires the full 2D table, so it’s incompatible with the 1D space optimisation.