Grid DP Fundamentals
Grid DP problems define a 2D state space where dp[i][j] represents some optimum property at cell (i, j). The recurrence uses adjacent cells (typically from the top and left for top-down traversal). Grid DP is a subtype of 2D DP — most grid problems reduce to: dp[i][j] = f(dp[i-1][j], dp[i][j-1], grid[i][j]). Recognizing the recurrence direction (top-left to bottom-right, or in reverse for path problems starting from the bottom-right) is the key first step.
Pattern 1: Unique Paths (LC 62, 63)
Count paths from (0,0) to (m-1, n-1) moving only right or down. dp[i][j] = number of ways to reach (i, j) = dp[i-1][j] + dp[i][j-1]. Base: dp[0][j] = 1 (only one way to reach any cell in the first row: keep going right). dp[i][0] = 1 (keep going down). With obstacles (LC 63): dp[i][j] = 0 if obstacle, else dp[i-1][j] + dp[i][j-1]. Space optimization: only need the current and previous row → O(n) space.
def unique_paths_with_obstacles(grid):
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = 1 # start if not blocked
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
dp[j] = 0 # obstacle
elif j > 0:
dp[j] += dp[j-1]
return dp[n-1]Pattern 2: Minimum Path Sum (LC 64)
Find the path from (0,0) to (m-1, n-1) with minimum total cost. dp[i][j] = min cost to reach (i, j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). In-place: modify grid directly (avoids extra space). Handle edges: first row has only one path (keep going right), first column only one path (keep going down).
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if i == 0 and j == 0: continue
top = grid[i-1][j] if i > 0 else float('inf')
left = grid[i][j-1] if j > 0 else float('inf')
grid[i][j] += min(top, left)
return grid[m-1][n-1]Pattern 3: Dungeon Game (LC 174)
A knight starts at (0,0), must reach (m-1, n-1). Each cell has a value (positive = health gained, negative = health lost). Knight dies if health drops to 0 or below at any point. Find the minimum initial health. Key insight: cannot solve left-to-right (greedy path maximizing health fails). Must solve right-to-left: dp[i][j] = minimum health needed when entering cell (i, j) to survive the rest of the dungeon.
def calculate_minimum_hp(dungeon):
m, n = len(dungeon), len(dungeon[0])
dp = [[float('inf')] * (n+1) for _ in range(m+1)]
dp[m][n-1] = dp[m-1][n] = 1 # sentinel: 1 health to enter the exit cell
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
min_health_after = min(dp[i+1][j], dp[i][j+1])
dp[i][j] = max(1, min_health_after - dungeon[i][j])
return dp[0][0]The formula max(1, next_needed – cell_value): if the cell has positive value, it reduces the health needed; if negative, increases it. Must be at least 1 (can’t start with 0 or negative health). This reverse-DP pattern appears whenever the constraint is about surviving a future state.
Pattern 4: Maximal Square and Triangle
Maximal Square (LC 221): find the largest square of 1s in a binary matrix. dp[i][j] = side length of the largest square with bottom-right corner at (i, j). If grid[i][j] == 1: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. If == 0: dp[i][j] = 0. The minimum of the three neighbors is the bottleneck — the square can only be as large as the smallest of the squares extending from the top, left, and top-left neighbors. Track the global maximum. O(mn) time and O(n) space (one row at a time). Cherry Pickup (LC 741): two passes on a grid (there and back). Key insight: model as two simultaneous walkers both starting at (0,0) and ending at (n-1, n-1). dp[t][r1][r2] where t = step count (r1 + c1 = r2 + c2 = t). O(n^3) states instead of O(n^4).
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Databricks Interview Prep