Grid DP
Intermediate · 16 min read · Problem-Solving Patterns, Dynamic Programming
Paths and costs on a grid, and how to save memory with one row.
Grid DP is the friendliest DP family because you can see the table: it's the grid itself. You move only right or down (usually), so a cell can only be reached from the cell above or the cell to the left — and its answer is built from theirs.
Unique paths — the template
State: dp[r][c] = number of ways to reach (r, c). Transition: dp[r][c] = dp[r − 1][c] + dp[r][c − 1]. Base: the first row and first column are all 1.
Obstacles
A blocked cell has zero ways to stand on it — that's the only change:
Minimum path sum — min instead of +
Counting uses +; optimising uses min/max. The edges are the only place you need care: cells in the top row have no "above", and cells in the left column have no "left".
Maximal square — a three-neighbour recurrence
State: dp[r][c] = side length of the largest all-1 square whose bottom-right corner is (r, c). A square ending here can only be as big as the smallest square ending at its three neighbours (top, left, top-left), plus one:
Dungeon game — fill backwards
Going forward fails: the best path to a cell depends on both the health you've lost and the health you have, which can't be combined into one number. Going backwards works: need[r][c] = minimum health needed when entering (r, c) to survive the rest. It depends only on the future, which is already computed.
Saving memory
Always mention the O(cols) space version — it's the standard follow-up question.
Practice ladder
Interview questions
- How do you reduce the space of the unique-paths DP to one row?
- Why does the dungeon game have to be solved from the bottom-right?
Further reading
Key takeaways
- In grid DP the table is the grid; each cell combines the cell above and the cell to the left.
- Counting → +; optimising → min/max; obstacles → 0.
- Pad the table with a zero row and column to remove edge cases.
- One row of memory is usually enough; save the diagonal when needed.
- If the forward state needs two numbers, fill backwards.