Intermediate

2D DP Problems

When the DP state requires two variables, we use a 2D table. These problems involve grids, two sequences, or two dimensions of choice. Five classic problems with complete solutions.

Problem 1: Unique Paths

Problem: A robot is at the top-left corner of an m x n grid. It can only move right or down. How many unique paths are there to the bottom-right corner?

State: dp[i][j] = number of unique paths to reach cell (i, j).

Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (arrive from above or from the left).

# Brute force: O(2^(m+n)) time
def unique_paths_brute(m, n):
    if m == 1 or n == 1:
        return 1
    return unique_paths_brute(m - 1, n) + unique_paths_brute(m, n - 1)

# Memoization: O(m*n) time, O(m*n) space
from functools import lru_cache

def unique_paths_memo(m, n):
    @lru_cache(maxsize=None)
    def dp(i, j):
        if i == 0 or j == 0:
            return 1
        return dp(i - 1, j) + dp(i, j - 1)
    return dp(m - 1, n - 1)

# Tabulation: O(m*n) time, O(n) space (row optimization)
def unique_paths_tab(m, n):
    dp = [1] * n  # First row is all 1s
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]  # dp[j] = above + left
    return dp[n - 1]

# Test: unique_paths_tab(3, 7) = 28

Problem 2: Minimum Path Sum

Problem: Given an m x n grid filled with non-negative numbers, find a path from top-left to bottom-right which minimizes the sum. You can only move right or down.

State: dp[i][j] = minimum path sum to reach cell (i, j).

Recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

# Brute force: O(2^(m+n)) time
def min_path_brute(grid, i=0, j=0):
    m, n = len(grid), len(grid[0])
    if i == m - 1 and j == n - 1:
        return grid[i][j]
    if i >= m or j >= n:
        return float('inf')
    return grid[i][j] + min(
        min_path_brute(grid, i + 1, j),
        min_path_brute(grid, i, j + 1)
    )

# Memoization: O(m*n) time, O(m*n) space
def min_path_memo(grid):
    m, n = len(grid), len(grid[0])
    memo = {}
    def dp(i, j):
        if i == m - 1 and j == n - 1:
            return grid[i][j]
        if i >= m or j >= n:
            return float('inf')
        if (i, j) in memo:
            return memo[(i, j)]
        memo[(i, j)] = grid[i][j] + min(dp(i + 1, j), dp(i, j + 1))
        return memo[(i, j)]
    return dp(0, 0)

# Tabulation: O(m*n) time, O(n) space
def min_path_tab(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = grid[0][0]
    # Fill first row
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]
    # Fill remaining rows
    for i in range(1, m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
    return dp[n - 1]

# Test: min_path_tab([[1,3,1],[1,5,1],[4,2,1]]) = 7 (1->3->1->1->1)

Problem 3: Edit Distance (Levenshtein Distance)

Problem: Given two strings word1 and word2, find the minimum number of operations (insert, delete, replace) to convert word1 into word2.

State: dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1].

Recurrence: If characters match, dp[i][j] = dp[i-1][j-1]. Otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) for delete, insert, replace.

# Brute force: O(3^(m+n)) time
def edit_brute(word1, word2, i=None, j=None):
    if i is None: i = len(word1)
    if j is None: j = len(word2)
    if i == 0: return j  # Insert remaining chars of word2
    if j == 0: return i  # Delete remaining chars of word1
    if word1[i-1] == word2[j-1]:
        return edit_brute(word1, word2, i-1, j-1)
    return 1 + min(
        edit_brute(word1, word2, i-1, j),    # Delete
        edit_brute(word1, word2, i, j-1),    # Insert
        edit_brute(word1, word2, i-1, j-1)   # Replace
    )

# Memoization: O(m*n) time, O(m*n) space
def edit_memo(word1, word2):
    memo = {}
    def dp(i, j):
        if i == 0: return j
        if j == 0: return i
        if (i, j) in memo: return memo[(i, j)]
        if word1[i-1] == word2[j-1]:
            memo[(i, j)] = dp(i-1, j-1)
        else:
            memo[(i, j)] = 1 + min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1))
        return memo[(i, j)]
    return dp(len(word1), len(word2))

# Tabulation: O(m*n) time, O(n) space
def edit_tab(word1, word2):
    m, n = len(word1), len(word2)
    # Space-optimized: only keep current and previous row
    prev = list(range(n + 1))  # Base case: edit distance from "" to word2[0..j]
    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:
                curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1])
        prev = curr
    return prev[n]

# Test: edit_tab("horse", "ros") = 3
# horse -> rorse (replace h with r)
# rorse -> rose (delete r)
# rose -> ros (delete e)
💡
Interview tip: Edit distance is one of the most commonly asked 2D DP problems. The key insight is that the three operations (insert, delete, replace) correspond to three adjacent cells in the DP table: left, above, and diagonal. Draw the table for small examples to build intuition.

Problem 4: Longest Common Subsequence (LCS)

Problem: Given two strings, find the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously.

State: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1].

Recurrence: If characters match, dp[i][j] = dp[i-1][j-1] + 1. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

# Brute force: O(2^(m+n)) time
def lcs_brute(text1, text2, i=None, j=None):
    if i is None: i = len(text1)
    if j is None: j = len(text2)
    if i == 0 or j == 0:
        return 0
    if text1[i-1] == text2[j-1]:
        return 1 + lcs_brute(text1, text2, i-1, j-1)
    return max(lcs_brute(text1, text2, i-1, j),
               lcs_brute(text1, text2, i, j-1))

# Tabulation: O(m*n) time, O(n) space
def lcs_tab(text1, text2):
    m, n = len(text1), len(text2)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev = curr
    return prev[n]

# Reconstruct the actual LCS string (needs full table)
def lcs_with_string(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] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # Backtrack to find the string
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if text1[i-1] == text2[j-1]:
            result.append(text1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return ''.join(reversed(result))

# Test: lcs_tab("abcde", "ace") = 3 ("ace")
# Test: lcs_with_string("abcde", "ace") = "ace"

Problem 5: Matrix Chain Multiplication

Problem: Given a sequence of matrices, find the most efficient way to multiply them. The order of multiplication affects the total number of scalar multiplications.

State: dp[i][j] = minimum cost to multiply matrices i through j.

Recurrence: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]) for all k in [i, j-1].

# Matrix dimensions: matrix i has dimensions dims[i] x dims[i+1]
# Example: dims = [10, 30, 5, 60] means three matrices:
#   A1 = 10x30, A2 = 30x5, A3 = 5x60

# Brute force: O(2^n) - Catalan number of parenthesizations
def mcm_brute(dims, i=1, j=None):
    if j is None: j = len(dims) - 1
    if i == j:
        return 0
    min_cost = float('inf')
    for k in range(i, j):
        cost = (mcm_brute(dims, i, k) +
                mcm_brute(dims, k + 1, j) +
                dims[i-1] * dims[k] * dims[j])
        min_cost = min(min_cost, cost)
    return min_cost

# Memoization: O(n^3) time, O(n^2) space
def mcm_memo(dims):
    n = len(dims) - 1
    memo = {}
    def dp(i, j):
        if i == j:
            return 0
        if (i, j) in memo:
            return memo[(i, j)]
        memo[(i, j)] = float('inf')
        for k in range(i, j):
            cost = dp(i, k) + dp(k + 1, j) + dims[i-1] * dims[k] * dims[j]
            memo[(i, j)] = min(memo[(i, j)], cost)
        return memo[(i, j)]
    return dp(1, n)

# Tabulation: O(n^3) time, O(n^2) space
def mcm_tab(dims):
    n = len(dims) - 1  # Number of matrices
    # dp[i][j] = min cost to multiply matrices i..j (1-indexed)
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    # Fill by chain length (l = 2 means pairs, l = 3 means triples, etc.)
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j]
                dp[i][j] = min(dp[i][j], cost)
    return dp[1][n]

# Test: mcm_tab([10, 30, 5, 60]) = 4500
# Optimal: (A1 * A2) * A3
# A1*A2 = 10*30*5 = 1500, result is 10x5
# (A1*A2)*A3 = 10*5*60 = 3000
# Total = 1500 + 3000 = 4500
# vs A1*(A2*A3) = 30*5*60 + 10*30*60 = 9000 + 18000 = 27000
📝
Pattern insight: Matrix chain multiplication is the foundational "interval DP" problem. The key is trying every possible split point k and taking the minimum. This same pattern appears in burst balloons, optimal BST, and palindrome partitioning (covered in Lesson 6).

Complexity Summary

ProblemBrute ForceDP TimeDP SpaceOptimized Space
Unique Paths O(2^(m+n)) O(m × n) O(m × n) O(n)
Min Path Sum O(2^(m+n)) O(m × n) O(m × n) O(n)
Edit Distance O(3^(m+n)) O(m × n) O(m × n) O(n)
LCS O(2^(m+n)) O(m × n) O(m × n) O(n)
Matrix Chain O(2^n) O(n^3) O(n^2) O(n^2)

Key Takeaways

  • 2D DP problems use two variables to define the state — typically two indices, grid coordinates, or positions in two strings.
  • Grid problems (unique paths, min path sum) have a natural left-to-right, top-to-bottom fill order and can be space-optimized to a single row.
  • Two-sequence problems (edit distance, LCS) compare characters from both strings and branch on match vs mismatch.
  • Matrix chain multiplication introduces interval DP: the state is a range [i, j] and we try every split point.
  • For all 2D problems, space can be reduced from O(m*n) to O(n) by keeping only the current and previous row.