# 2D Dynamic Programming Interview Patterns: LCS, Edit Distance, Knapsack, Grid Paths (2025)

Source: https://www.techinterview.org/post/3233464842/two-dimensional-dp-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## When to Use 2D DP

2D DP uses a table dp[i][j] where i and j represent positions in two sequences, or dimensions of a problem. Common patterns: comparing two strings (LCS, Edit Distance, Regex Matching), 2D grid traversal (unique paths, minimum path sum), unbounded/0-1 knapsack variants, and interval DP (problems on subarrays).

## Longest Common Subsequence (LCS)

dp[i][j] = length of LCS of s1[:i] and s2[:j]. Base case: dp[0][j] = dp[i][0] = 0 (empty string). Transition: if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1. Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Fill row by row. O(m*n) time and space. Space optimization: only need the previous row, O(min(m,n)) space. LCS is the foundation for: Longest Common Substring (track the max while building the table), Shortest Common Supersequence (m+n-LCS), Minimum deletions to make strings equal (m+n-2*LCS).


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


## Edit Distance (LC 72)

dp[i][j] = minimum operations (insert, delete, replace) to convert s1[:i] to s2[:j]. Base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all). Transition: if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (no op). Else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete from s1, insert into s1, replace). dp[m][n] is the answer. Space: optimize to O(n) using two rows.

## 0-1 Knapsack

dp[i][w] = max value using items 0..i with weight capacity w. Transition: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w else dp[i-1][w]. O(n*W) time and space. Space optimization: iterate weights in reverse (right to left) to use a 1D array (current item can only use each previous state once). Unbounded knapsack (items can be reused): iterate weights left to right in the 1D array.

## Unique Paths (LC 62)

Grid m x n, move only right or down. dp[i][j] = dp[i-1][j] + dp[i][j-1]. Base case: dp[0][j] = dp[i][0] = 1 (only one way to reach any edge cell). O(m*n) time, O(n) space (single row). With obstacles (LC 63): dp[i][j] = 0 if obstacle, else dp[i-1][j] + dp[i][j-1]. Mathematical formula for LC 62 without DP: C(m+n-2, m-1) -- choosing which m-1 of the m+n-2 steps are "down".

## Coin Change II (LC 518) -- Unbounded Knapsack Variant

Count number of ways to make amount using coins (unlimited supply). dp[j] = number of ways to make amount j. For each coin: for j from coin to amount: dp[j] += dp[j-coin]. Outer loop over coins, inner over amounts (not the other way) -- this ensures each coin can be used unlimited times and combinations are counted without repetition (order does not matter). O(n * amount) time, O(amount) space.

## Interval DP: Burst Balloons (LC 312)

dp[i][j] = max coins by bursting all balloons between i and j (exclusive of i and j). For each subproblem size (length of interval), for each k between i and j: dp[i][j] = max(dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]). k is the LAST balloon burst in [i+1, j-1] -- when k is burst last, i and j are still present as its neighbors. Start from smaller subproblems and build up. O(n^3) time, O(n^2) space.

Asked at: [Meta Interview Guide](https://techinterview.org/meta-interview/)

Asked at: [Apple Interview Guide](https://techinterview.org/apple-interview/)

Asked at: [LinkedIn Interview Guide](https://techinterview.org/linkedin-interview/)

Asked at: [Coinbase Interview Guide](https://techinterview.org/coinbase-interview/)