Grid DP Overview
Grid DP problems involve a 2D grid where you make decisions at each cell and need to find an optimal or count-based answer. The DP state is dp[i][j] representing the answer for the subproblem ending at cell (i, j). Transitions come from adjacent cells (typically up and left for top-down-left-to-right movement). Grid DP appears in ~10% of LeetCode hard problems and is a FAANG staple.
Unique Paths (LC 62)
Count paths from top-left to bottom-right of an m×n grid, moving only right or down. dp[i][j] = dp[i-1][j] + dp[i][j-1] (paths coming from above + paths coming from left). Base cases: dp[0][j] = 1 (top row — only one way: move all right), dp[i][0] = 1 (left column — only one way: move all down). Fill row by row. Answer: dp[m-1][n-1]. Time O(m×n), space O(m×n), reducible to O(n) using a 1D rolling array (dp[j] = dp[j] + dp[j-1]).
Math shortcut: the answer is C(m+n-2, m-1) — choose m-1 down moves out of m+n-2 total moves. For large grids this avoids DP entirely.
Minimum Path Sum (LC 64)
Find the path from top-left to bottom-right (right/down only) with minimum sum of cell values. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Border initialization: first row = prefix sums (can only come from left), first column = prefix sums (can only come from above). In-place modification: modify grid directly instead of allocating dp array (O(1) extra space).
Triangle (LC 120)
Find minimum path sum from top to bottom of a triangle, moving to adjacent numbers in the row below. Bottom-up: start from the second-to-last row and update each element dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]). After processing, dp[0][0] is the answer. Space O(n) using the last row as the DP array, modified in place.
Dungeon Game (LC 174)
Find the minimum initial health to rescue the princess, moving right/down through a dungeon where cells add or subtract health. This problem requires backward DP — work from the princess’s room (bottom-right) back to the start. dp[i][j] = minimum health needed when entering cell (i, j). dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) – dungeon[i][j]). The max(1) ensures health never drops below 1. Fill from bottom-right to top-left. Answer: dp[0][0]. Why backward? Forward DP cannot determine the minimum health needed at the start because health at any point depends on all future cells.
Maximal Square (LC 221)
Find the largest square containing only 1s in a binary matrix. dp[i][j] = side length of the largest all-1s square with bottom-right corner at (i, j). If matrix[i][j] == ‘0’: dp[i][j] = 0. If matrix[i][j] == ‘1’: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. Intuition: a square can be extended only as far as all three neighboring squares allow — the bottleneck is the smallest of the three. Answer: max(dp)^2. Time O(m×n), space O(m×n) or O(n) with rolling array.
Longest Increasing Path in a Matrix (LC 329)
Find the longest strictly increasing path in a matrix, moving in 4 directions (no diagonals). Memoized DFS: for each cell, DFS in all 4 directions to cells with strictly larger values. dp[i][j] = longest increasing path starting at (i, j). Result is max over all cells. Since paths are strictly increasing and cycles are impossible (strictly increasing cannot cycle), no visited tracking is needed — every subpath terminates at a local maximum. Time O(m×n), space O(m×n) for memo + O(m×n) for recursion stack.
Cherry Pickup (LC 741) — Hard
Two robots traverse a grid simultaneously, collecting cherries. The key insight: instead of modeling two separate paths (which is exponential), model them as two robots starting at (0,0) simultaneously moving down/right, reaching (n-1,n-1) at the same time. State: dp[t][r1][r2] where t = steps taken, r1 = row of robot 1, r2 = row of robot 2. Column of each robot is determined by t and row (c = t – r). Since both make t steps, only 3 parameters suffice. Cherry is counted once even if both visit the same cell. Space optimization: dp[r1][r2] at each step t — O(n²) space.
Grid DP Pattern Recognition
- Right/down only, count paths or find optimal: standard forward DP (top-left → bottom-right)
- Depends on future cells (dungeon game, cherry pickup with return): backward DP or multi-pass
- 4-direction movement with cycles: memoized DFS (need recursion structure; DP table may need topological sort)
- Square/rectangle substructures: maximal square, maximal rectangle (histogram per row)
- Two traversals simultaneously: 3D DP state (t, r1, r2) with dimension reduction
Space Optimization
Most grid DP problems can reduce from O(m×n) to O(n) space: since dp[i][j] only depends on dp[i-1][…] and dp[i][j-1], only the current and previous row are needed. Maintain a 1D array dp[j] and update left to right (or right to left, depending on transition direction). For problems with backward DP (dungeon game), iterate bottom to top and right to left.