Grid DP
In one line
In grid DP each cell's answer comes from the neighbours you could have arrived from, usually the cell above and the cell to the left, filled row by row.
What it is
Grid DP problems ask for the number of paths, the cheapest path or the largest shape in a 2D grid where movement is restricted, typically only right or down. Because you can only arrive from a few directions, dp[r][c] depends on a few already-computed cells.
Unique paths counts routes from the top-left to the bottom-right: dp[r][c] = dp[r-1][c] + dp[r][c-1]. Minimum path sum finds the cheapest route: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]). Obstacles simply set dp to 0 (for counting) or infinity (for costs).
Since each row only needs the row above, you can keep a single 1D array of length cols and update it in place, cutting memory from O(rows x cols) to O(cols).
Why interviewers ask
Grid problems make DP visual, so interviewers use them to see whether you can define dp[r][c] precisely, handle the first row and column edge cases, and optimise space. Variations such as obstacles, maximal square or a path that must be computed backwards (dungeon game) test whether you understand the dependency direction rather than memorising code.
How it works
- 1Define dp[r][c] in words, for example 'the minimum cost to reach cell (r, c) from (0, 0)'.
- 2Write the transition from the allowed previous cells. For right/down movement, those are (r-1, c) and (r, c-1).
- 3Initialise the edges: the first row can only be reached from the left, the first column only from above.
- 4Fill row by row, left to right, so both dependencies are ready. The answer is the bottom-right cell.
- 5Space: keep one array dp of length cols. Before updating, dp[c] still holds the value from the row above and dp[c-1] already holds the current row's left neighbour.
Worked example · Minimum path sum on a 3x3 grid
- Grid rows: [1, 3, 1], [1, 5, 1], [4, 2, 1]. Move only right or down.
- Row 0 (only from the left): 1, 1+3 = 4, 4+1 = 5. dp = [1, 4, 5].
- Row 1: column 0 only from above: 1+1 = 2. Column 1: min(4 above, 2 left) + 5 = 7. Column 2: min(5, 7) + 1 = 6. dp = [2, 7, 6].
- Row 2: column 0: 2+4 = 6. Column 1: min(7, 6) + 2 = 8. Column 2: min(6, 8) + 1 = 7. dp = [6, 8, 7].
- Answer 7, along the path 1 > 3 > 1 > 1 > 1 (right, right, down, down).
- Unique paths on the same 3x3 grid gives rows [1,1,1], [1,2,3], [1,3,6], so 6 paths.
Picture it
Picture a city of one-way streets that only go east or south. The cheapest taxi fare to any corner is the cheaper of the fares to the corner just north or just west, plus this block's toll. Fill in fares block by block from the top-left and the bottom-right corner gives the answer.
Reference code
def min_path_sum(grid):
"""Min sum path from top-left to bottom-right, moving right or down."""
rows, cols = len(grid), len(grid[0])
dp = [0] * cols # dp[c] = best cost to reach (r, c)
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
dp[c] = grid[0][0]
elif r == 0:
dp[c] = dp[c - 1] + grid[r][c] # only from the left
elif c == 0:
dp[c] = dp[c] + grid[r][c] # only from above
else:
dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
return dp[-1]
def unique_paths(m, n):
row = [1] * n
for _ in range(1, m):
for c in range(1, n):
row[c] += row[c - 1] # above (old row[c]) + left
return row[-1]
# min_path_sum([[1,3,1],[1,5,1],[4,2,1]]) -> 7
# unique_paths(3, 7) -> 28
min_path_sum keeps one row: dp[c] before the update is the cell above, dp[c-1] is the cell to the left. unique_paths uses the same rolling row. Both are O(rows x cols) time and O(cols) space.
Key patterns
Counting paths
When: Number of routes with right/down moves, possibly with obstacles
How: dp[r][c] = dp[r-1][c] + dp[r][c-1]; obstacle cells are 0.
Min or max cost path
When: Cheapest or most valuable monotone path
How: dp[r][c] = grid[r][c] + min (or max) of the allowed predecessors.
Maximal square
When: Largest square of 1s in a binary matrix
How: If cell is 1: dp[r][c] = 1 + min(top, left, top-left); answer is the max squared.
Fill backwards (dungeon game)
When: The constraint depends on the future, like minimum starting health
How: Fill from the bottom-right to the top-left: need[r][c] = max(1, min(need right, need down) - grid[r][c]).
Triangle / falling path
When: Each row's cell reaches 2 or 3 cells in the next row
How: Same idea with different neighbours; often solved bottom-up to end with one value.
Real-world use
Content-aware image resizing
Seam carving, introduced by Avidan and Shamir and the idea behind content-aware scaling in image editors, finds the lowest-energy vertical path of pixels with a grid DP where each pixel takes the minimum of three cells above.
Sequence alignment and diff
Edit distance and DNA alignment are grid DPs over two sequences; each cell depends on the cells above, left and diagonal.
Robot and game path costs
Tile-based games and warehouse robots with restricted moves compute cheapest routes over cost maps with grid DP when movement is monotone; general movement needs Dijkstra or A* instead.
Image analysis
The maximal square DP (largest all-ones square) and summed-area tables (2D prefix sums) are used in computer vision, for example summed-area tables in the Viola-Jones face detector to compute rectangle sums in O(1).
In a project
A farm-drone startup needs flight paths over a field split into a 200 x 300 grid of cells, each with an estimated wind and battery cost. The drone flies from the north-west corner to the south-east corner moving only east or south to spray in strips.
- Build a cost grid from the weather and terrain data, one value per cell.
- Run minimum path sum with a 1D rolling array to get the cheapest cost.
- Keep a separate full table of directions (came from left or from above) so the actual route can be reconstructed backwards from the goal.
- Mark no-fly cells as infinite cost and report when no path exists.
Impact: Each route is computed in O(rows x cols), about 60,000 cell updates, which is instant, and battery use per flight drops compared with a fixed zigzag pattern; the team can rerun it whenever the wind forecast changes.
Trade-offs
Use it when
- Movement is monotone (only right/down, or row to next row)
- You need path counts, min/max cost, or largest shapes in a matrix
- The grid fits in memory and O(rows x cols) is acceptable
Avoid it when
- You can move in all four directions: cycles break the fill order, use BFS or Dijkstra
- Costs can be negative with arbitrary movement (needs Bellman-Ford style methods)
- Only reachability is asked with free movement: plain BFS/DFS is simpler
Cost: O(rows x cols) time; O(rows x cols) space with the full table, O(cols) with a rolling row (keep the full table if you must reconstruct the path).
Common mistakes
- Forgetting to initialise the first row and first column specially.
- Using grid DP when moves go in all four directions; there is no valid fill order.
- In the rolling array, iterating columns right to left when you need the current row's left neighbour.
- For obstacles, setting the start cell to 1 even when the start itself is blocked.
- Filling dungeon game forwards; the minimum health requirement must be computed from the goal backwards.
Interview questions
Quick revision
- dp[r][c] from (r-1, c) and (r, c-1) for right/down moves.
- First row: only from the left. First column: only from above.
- Paths: add. Costs: min. Maximal square: 1 + min of three.
- Rolling row: O(cols) space.
- Unique paths m x n = C(m+n-2, m-1).
- Dungeon game: fill backwards from the goal.
- Four-direction movement: BFS or Dijkstra, not grid DP.
Check yourself
1. How many unique right/down paths are there in a 3 x 3 grid?
2. Minimum path sum for [[1,3,1],[1,5,1],[4,2,1]]?
3. When is grid DP the wrong tool?
4. In maximal square, what is dp[r][c] for a cell with value 1?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.