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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the recurrence relation for Unique Paths and why does it work?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Unique Paths (LC 62) asks for the number of distinct paths from top-left to bottom-right of an mu00d7n grid, moving only right or down. The recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1]. Intuition: to reach cell (i, j), you must come either from cell (i-1, j) directly above, or cell (i, j-1) directly to the left u2014 these are the only two valid previous positions. The total number of ways to reach (i, j) is the sum of ways to reach each predecessor. Base cases: dp[0][j] = 1 for all j (only one way to reach any cell in the top row: move all the way right from the start). dp[i][0] = 1 for all i (only one way to reach any cell in the left column: move all the way down). Fill row by row, left to right. Space can be reduced from O(mu00d7n) to O(n): since dp[i][j] depends only on dp[i-1][j] (above, already computed in current row) and dp[i][j-1] (left, just computed this iteration), a 1D array dp[j] = dp[j] + dp[j-1] works u2014 dp[j] before update holds the value from the row above.”
}
},
{
“@type”: “Question”,
“name”: “Why does the Dungeon Game require backward DP rather than forward DP?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The Dungeon Game (LC 174) requires backward DP because the decision of how much health is needed at each cell depends on the cells visited afterward, not before. In forward DP (left-to-right, top-to-bottom), dp[i][j] would represent something like “minimum health when arriving at (i,j).” But knowing the minimum health at (i,j) doesn’t help you determine the minimum initial health, because future cells might drain more health than you have. The knight can always heal, so the path through high-healing rooms early might allow negative rooms later u2014 forward DP can’t capture this correctly without tracking more state. Backward DP defines dp[i][j] = minimum health needed upon entering cell (i,j) to guarantee survival to the princess room. Recurrence: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) – dungeon[i][j]). If dungeon[i][j] is positive (health gain), entering with 1 health and gaining dungeon[i][j] gives more than needed. If negative (damage), you need at least (min_needed_next – dungeon[i][j]) health to survive. max(1,…) ensures health never drops to 0 or below. Fill from bottom-right to top-left. dp[0][0] is the answer.”
}
},
{
“@type”: “Question”,
“name”: “How does the Maximal Square DP work and what is the intuition behind the recurrence?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Maximal Square (LC 221) finds the largest all-1 square in a binary matrix. dp[i][j] = side length of the largest all-1 square with its bottom-right corner at (i,j). Recurrence: if matrix[i][j] == ‘0’: dp[i][j] = 0 (can’t form a square ending here). 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 of side s with bottom-right corner at (i,j) requires: (1) a square of side s-1 ending at (i-1,j) u2014 the cell above has an (s-1) u00d7 (s-1) all-1 square above. (2) A square of side s-1 ending at (i,j-1) u2014 the cell to the left has an (s-1) u00d7 (s-1) all-1 square to the left. (3) A square of side s-1 ending at (i-1,j-1) u2014 the diagonal cell. The minimum of the three determines the largest square we can guarantee. If dp[i-1][j]=3, dp[i][j-1]=3, dp[i-1][j-1]=2, then the constraint is the 2u00d72 diagonal square u2014 we can only guarantee a 3u00d73 square overall (2+1=3… actually min=2, so 2+1=3). The minimum is the bottleneck: even if two sides allow a large square, the third must agree. The area is dp[i][j]u00b2. Track max dp[i][j] across all cells.”
}
}
]
}