DP — Grid Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide
Each cell's answer comes from its neighbours above and to the left. Fill the table row by row.
2 sub-patterns · 7 questions
What is this pattern?
Grid DP: the state is a cell (r, c), and dp[r][c] is the answer for the part of the grid that ends at that cell. You fill the table row by row, left to right, so the cells it needs (above, left, above-left) are already done.
Two shapes cover almost every question:
- Paths: you can only move right / down (or down to one of three cells). To reach
(r, c)you came from the cell above or the cell to the left, sodp[r][c] = dp[r − 1][c] + dp[r][c − 1](number of ways) orgrid[r][c] + min(…)(cheapest path). - Shapes:
dp[r][c]= the biggest shape whose corner is(r, c). A square of sidekending here needs squares of sidek − 1ending above, to the left and diagonally:1 + min(top, left, top-left).
Edges first: the first row and column have only one neighbour, and obstacles or out-of-grid cells contribute nothing. Since each row only reads the row above, the table shrinks to one row of size N.
Filling in a city map of street corners, starting at the top-left. To know how many routes reach a corner, you only need the numbers already written on the corner just north and the corner just west of it — add them and write the sum down.
See it move
Purple = the two cells the rule reads. Red = the obstacle (0 ways). Each cell is filled once: O(M · N).
3 × 4 grid, obstacle at (1, 1)step 1/13dp[r][c] = the number of ways to reach (r, c) moving only right or down. Row by row, left to right, the cell above and the cell to the left are always done first.
Purple = top, left and top-left. Gold = a new biggest square. The answer is the max over all cells, not the last cell.
4 × 4 matrix of 0s and 1sstep 1/18dp[r][c] = the side of the biggest all-1 square whose bottom-right corner is (r, c). A 0 cell is 0. Grey cells in the matrix are 0s.
How do I recognise it?
A 2-D grid and you may move only right / down (or down-left / down / down-right).
"Number of unique paths", "minimum path sum / cost" from the top-left to the bottom-right (or from the top row to the bottom row).
Obstacles that block cells.
"Largest square of 1s", "count square submatrices" — the biggest shape with its corner at each cell.
A triangle or staircase of numbers where each step goes to one of a few cells below.
Looks like DP — Grid, but isn't
With up / left moves allowed, cells can depend on each other in a cycle, so there is no fill order. DP needs moves that only go forward (right / down).
That's about connectivity, not about an answer built from neighbours above and to the left.
Grid DP counts or optimises. The number of paths grows exponentially, so listing them is a search, not a table.
A square only needs its three neighbours; a rectangle can have any width and height, so build a histogram per row and use the largest-rectangle stack.
How would I discover it from scratch?
Don't memorise “use dp — grid”. Ask these questions in order — the pattern falls out.
Recurse from the target: paths(r, c) = paths(r − 1, c) + paths(r, c − 1). Every call branches in two, so it costs about O(2^(M+N)).
Sub-patterns
Same core idea, different rule for “valid”. Learn them in this order.
Paths in a grid
5 questionsdp[r][c] = the number of ways (or the cheapest cost) to reach (r, c), built from the cells you could have come from.
Squares and shapes
2 questionsdp[r][c] = the biggest shape with its corner at (r, c). For squares: 1 + min(top, left, top-left) on a 1-cell, 0 on a 0-cell.
Don't mix these up
Moves only right / down (a DAG) → DP in row order. Moves in all four directions → BFS / Dijkstra.
Same table and order. Counting adds the two neighbours; cost takes the smaller one and adds this cell's cost.
Same dp. The first answers with max(dp)² (area), the second with sum(dp) — a cell with value 3 is the corner of 3 squares (sides 1, 2, 3).
Top-down needs special cases at both edges of each row and a min over the last row. Bottom-up starts from the last row and ends with the answer in one cell.
Code templates (C++)
Paths (ways / min cost) in one row
Change one line: + for counting ways, min(...) + cost for the cheapest path. Obstacles set the cell to 0 (ways) or skip it (cost).
// Grid paths in one row: moves go right or down only.
// Before the update dp[c] is the cell ABOVE; dp[c - 1] is already the new cell to the LEFT.
// Number of ways from the top-left to the bottom-right (1 = blocked).
long long countPaths(const vector<vector<int>>& blocked) {
int m = blocked.size(), n = blocked[0].size();
vector<long long> dp(n, 0);
dp[0] = 1;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (blocked[r][c]) dp[c] = 0; // no path goes through an obstacle
else if (c > 0) dp[c] += dp[c - 1]; // above (old dp[c]) + left (dp[c - 1])
}
return dp[n - 1];
}
// Cheapest path: same order, min instead of +.
int minPathCost(const vector<vector<int>>& cost) {
int m = cost.size(), n = cost[0].size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
int best = dp[c]; // from above
if (c > 0) best = min(best, dp[c - 1]); // from the left
dp[c] = best + cost[r][c];
}
return dp[n - 1];
}Largest square ending here
Keep the old top-left value in diag before overwriting dp[c]. Sum all dp values to count squares instead of finding the largest.
// dp[c + 1] (current row) = side of the largest all-1 square whose bottom-right corner is (r, c).
// It is 1 + min(top, left, top-left); top-left is saved in `diag` before it is overwritten.
int largestSquareSide(const vector<vector<char>>& g) {
int m = g.size(), n = g[0].size(), best = 0;
vector<int> dp(n + 1, 0); // dp[c + 1] is column c; dp[0] stays 0
for (int r = 0; r < m; r++) {
int diag = 0; // top-left of the cell being filled
for (int c = 0; c < n; c++) {
int top = dp[c + 1]; // still the previous row's value
dp[c + 1] = g[r][c] == '1' ? 1 + min({top, dp[c], diag}) : 0;
diag = top;
best = max(best, dp[c + 1]); // sum dp[c + 1] instead to COUNT squares
}
}
return best; // the area is best * best
}