2D DP Pattern Overview
2D dynamic programming problems use a 2D table where dp[i][j] represents the optimal value considering only the first i rows and j columns (or first i characters of string 1 and j characters of string 2). The key is defining what dp[i][j] means precisely, establishing base cases for empty prefixes, and identifying the recurrence from neighbors.
Unique Paths (LC 62)
Count paths from top-left to bottom-right of an m x n grid, moving only right or down.
def uniquePaths(m: int, n: int) -> int:
# dp[i][j] = number of ways to reach cell (i, j)
# can only arrive from above (i-1,j) or from the left (i,j-1)
dp = [[1] * n for _ in range(m)] # base case: first row and col = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Space optimization: current row depends only on previous row
def uniquePaths_O_n(m: int, n: int) -> int:
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # dp[j] still holds prev row value before update
return dp[n-1]Time O(mn), space O(mn) full table or O(n) with rolling array. Base case: every cell in the first row and first column has exactly 1 path (only one way to reach them – all right or all down).
Unique Paths with Obstacles (LC 63)
Same recurrence, but obstacle cells get dp[i][j] = 0, and base case initialization must skip obstacles.
def uniquePathsWithObstacles(grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
# First column: once you hit an obstacle, all cells below are 0
for i in range(m):
if grid[i][0] == 1:
break
dp[i][0] = 1
# First row: same idea horizontally
for j in range(n):
if grid[0][j] == 1:
break
dp[0][j] = 1
for i in range(1, m):
for j in range(1, n):
if grid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]Minimum Path Sum (LC 64)
Find the path from top-left to bottom-right (moving right or down) with the minimum sum of grid values.
def minPathSum(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 j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
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]Maximal Square (LC 221)
Find the largest square of ‘1’s in a binary matrix. dp[i][j] = side length of the largest square whose bottom-right corner is at (i, j).
def maximalSquare(matrix: list[list[str]]) -> int:
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
max_side = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
# The bottleneck is the smallest of the three neighbors
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
max_side = max(max_side, dp[i][j])
return max_side * max_sideWhy does min of 3 neighbors work? For a square of side k+1 to exist at (i,j), you need: a square of side k above (i-1,j), a square of side k to the left (i,j-1), and a square of side k diagonally (i-1,j-1). The minimum of those three is the largest square that fits in all directions simultaneously. If any neighbor is smaller, that direction limits the square size.
Dungeon Game (LC 174)
The knight starts top-left and must reach bottom-right, maintaining HP > 0 at every cell. Cells have positive (health gain) or negative (damage) values. Find the minimum initial HP needed.
Forward DP fails here because a cell’s optimal HP depends on future cells. Fill from bottom-right to top-left: dp[i][j] = minimum HP the knight needs when entering cell (i,j) to survive the rest of the dungeon.
def calculateMinimumHP(dungeon: list[list[int]]) -> int:
m, n = len(dungeon), len(dungeon[0])
dp = [[0] * n for _ in range(m)]
# Bottom-right: must have at least 1 HP after the cell
dp[m-1][n-1] = max(1 - dungeon[m-1][n-1], 1)
# Last row: can only go right
for j in range(n-2, -1, -1):
dp[m-1][j] = max(dp[m-1][j+1] - dungeon[m-1][j], 1)
# Last column: can only go down
for i in range(m-2, -1, -1):
dp[i][n-1] = max(dp[i+1][n-1] - dungeon[i][n-1], 1)
# Fill rest bottom-right to top-left
for i in range(m-2, -1, -1):
for j in range(n-2, -1, -1):
min_hp_next = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(min_hp_next - dungeon[i][j], 1)
return dp[0][0]The min(1, …) ensures HP never drops below 1. The direction reversal is the key insight: what matters is the HP required from the current position forward, not accumulated from the past.
Interleaving String (LC 97)
Given s1, s2, s3, determine if s3 is formed by interleaving s1 and s2 (preserving relative order in each). dp[i][j] = true if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1].
def isInterleave(s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or
(dp[i][j-1] and s2[j-1] == s3[i+j-1])
return dp[m][n]Triangle (LC 120)
Find the minimum path sum from top to bottom of a triangle. Each step can move to adjacent numbers in the row below. Fill from bottom to top using a 1D array.
def minimumTotal(triangle: list[list[int]]) -> int:
n = len(triangle)
dp = triangle[-1][:] # start with the last row values
# Work upward from second-to-last row
for i in range(n - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
return dp[0]Space O(n) by reusing the dp array in place. No 2D table needed because each row depends only on the row below.
Space Optimization: Rolling Arrays
Most 2D DP recurrences only look at the previous row (or previous column). This means you do not need to keep the full m x n table – just two rows (or one row updated carefully).
Pattern for one-row update (when dp[i][j] depends on dp[i-1][j] and dp[i][j-1]):
# Two-row approach (clearer)
prev = [base_case_values]
for i in range(1, m):
curr = [0] * n
curr[0] = ... # base case for new row
for j in range(1, n):
curr[j] = recurrence(prev[j], curr[j-1])
prev = curr
# Single-row approach (for simple left+above recurrences)
dp = [base_case_values_for_row_0]
for i in range(1, m):
for j in range(1, n):
dp[j] = recurrence(dp[j], dp[j-1])
# dp[j] before update = prev row value (above)
# dp[j-1] after update = current row value (left)When the recurrence also looks at dp[i-1][j-1] (the diagonal, as in Maximal Square), you need to save that value before overwriting it. Use a variable “prev_diagonal” to track dp[i-1][j-1] as you iterate left to right.
Common Pattern Summary
Define dp[i][j] as “the optimal value when considering only the first i rows and j columns” (or first i and j characters for string problems). This definition naturally handles base cases: dp[0][j] and dp[i][0] represent empty prefixes, which are usually trivial (0 paths, 0 cost, or true/false depending on the problem).
Base cases fill the first row and first column before the main loops. They represent edge conditions: can only reach (i,0) by going straight down, can only reach (0,j) by going straight right.
Direction matters – most grid problems fill top-left to bottom-right. Dungeon Game fills bottom-right to top-left because the optimal choice depends on the future, not the past. When you are minimizing the starting cost of a forward journey, reverse the direction.
Interview approach: state the dp definition out loud before writing code. Draw the small example table to verify the recurrence. Identify the base cases. Code the full O(mn) solution first, then discuss space optimization if asked.
Meta coding interviews test 2D DP patterns. See common questions for Meta interview: 2D grid DP problems.
Apple coding rounds include 2D DP problems including grid paths and squares. See patterns for Apple interview: dynamic programming on grids.
Databricks interviews include 2D DP patterns. See common questions for Databricks interview: 2D DP and matrix problems.