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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you count unique paths in a grid (LC 62)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[i][j] = number of unique paths to reach cell (i,j) from (0,0) moving only right or down. Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (came from above or from the left). Base cases: dp[0][j] = 1 for all j (only one way to reach any cell in the first row – keep going right). dp[i][0] = 1 for all i (only one way to reach any cell in the first column – keep going down). Final answer: dp[m-1][n-1]. Space optimization: since dp[i][j] only depends on the current row and the row above, use a 1D array updated left to right. dp[j] += dp[j-1] after initialization. This reduces space from O(m*n) to O(n). The math formula is C(m+n-2, m-1) but DP is cleaner in interviews.”}},{“@type”:”Question”,”name”:”What is the insight behind the Maximal Square problem (LC 221)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[i][j] = side length of the largest square whose bottom-right corner is at (i,j). If matrix[i][j] == '0': dp[i][j] = 0. If matrix[i][j] == '1': dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). The minimum of the three neighbors is taken because: a square of side k at (i,j) requires squares of side >= k-1 at (i-1,j), (i,j-1), and (i-1,j-1). The minimum neighbor limits how large the square can be. Example: if the top, left, and diagonal neighbors have side lengths 3, 3, and 1, the square can only extend to side 2 (limited by the diagonal). Track the global maximum during the DP. Time O(m*n), space O(m*n) reducible to O(n).”}},{“@type”:”Question”,”name”:”How do you solve the Dungeon Game (LC 174) with DP?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The knight needs minimum HP to start and must survive at each cell (HP >= 1). If you fill the DP table from top-left to bottom-right, you do not know future cells' effects. Fill from bottom-right to top-left. dp[i][j] = minimum HP needed when entering cell (i,j). For the destination cell: dp[m-1][n-1] = max(1, 1 – dungeon[m-1][n-1]) (need at least 1 HP, more if the cell drains HP). For other cells: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) – dungeon[i][j]). min() chooses the better next cell. max(1, …) ensures HP is always at least 1. The answer is dp[0][0]. The reverse direction is the key insight: only by knowing the cost of future cells can we determine the minimum entry HP.”}},{“@type”:”Question”,”name”:”How do you solve Interleaving String (LC 97)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”dp[i][j] = True if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]. Recurrence: dp[i][j] = (s1[i-1] == s3[i+j-1] AND dp[i-1][j]) OR (s2[j-1] == s3[i+j-1] AND dp[i][j-1]). The first condition: use the last character of s1. The second: use the last character of s2. Base: dp[0][0] = True (both empty). dp[i][0] = s1[0..i-1] == s3[0..i-1] (only s1 contributes). dp[0][j] = s2[0..j-1] == s3[0..j-1]. Time O(m*n). Early exit: if len(s1) + len(s2) != len(s3), return False immediately. Space optimization to O(n) with a rolling row is straightforward.”}},{“@type”:”Question”,”name”:”What is the rolling array technique for 2D DP space optimization?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Most 2D DP recurrences of the form dp[i][j] = f(dp[i-1][…], dp[i][…]) only depend on the previous row and the current row. Instead of storing all rows, keep only two rows: prev and curr. After each row, set prev = curr. Reduces space from O(m*n) to O(n). For recurrences that depend only on the previous row (not the current row): a single 1D array works if you update from right to left (so old values are not overwritten before use). Left-to-right update: dp[j] = f(dp[j], dp[j-1]) – reads old dp[j] (previous row) and new dp[j-1] (current row). When to use right-to-left: when dp[i][j] depends on dp[i][j-1] – updating right-to-left preserves dp[i-1][j-1] until needed.”}}]}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.