On this page
Description
Grid tabulation fills a table the shape of the grid. Each cell holds an answer, such as the number of paths to it or the cheapest cost to reach it. That answer is built from the cells above it and to its left, which were filled first. That turns an exponential "try every path" search into one O(rows x cols) pass. It's also the shape behind edit distance, longest common subsequence and many other 2D DP problems.
We'll go from simple to more technical:
- The pattern: base cases on the edges, then each cell from its neighbors.
- A second flavor: one rolling row instead of the whole table.
- Where the same table-filling runs in production (diff tools, sequence alignment).
- The bugs: wrong base cases, the wrong fill order, and Python's shared rows.
The approach
How many ways are there to walk from the top-left corner to the bottom-right, moving only right or down? Trying every path is exponential. But you can only arrive at a cell from above or from the left. So the number of ways to reach a cell is the ways to reach the cell above plus the ways to reach the cell to its left. Cells on the top row or left column can be reached only one way: straight along the edge.
Filling a grid with 3 rows and 4 columns, row by row:
| Column 0 | Column 1 | Column 2 | Column 3 | |
|---|---|---|---|---|
| Row 0 | 1 | 1 | 1 | 1 |
| Row 1 | 1 | 2 | 3 | 4 |
| Row 2 | 1 | 3 | 6 | 10 |
The bottom-right corner can be reached 10 ways. Its 10 is 4 (from above) plus 6 (from the left).
Java
int[][] dp = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (r == 0 || c == 0) {
dp[r][c] = 1; // base case: one way along an edge
} else {
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]; // combine the two cells this one depends on
}
}
}
return dp[rows - 1][cols - 1];
Python
def unique_paths(rows: int, cols: int) -> int:
dp = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if r == 0 or c == 0:
dp[r][c] = 1 # base case: one way along an edge
else:
dp[r][c] = dp[r - 1][c] + dp[r][c - 1] # combine the two cells this one depends on
return dp[rows - 1][cols - 1]
It's Pascal's Triangle turned on its side. Each cell combines cells already filled, so one ordered pass builds the whole table, with no recursion.
A second flavor: one rolling row
A cell needs only the cell above it and the cell to its left, never anything two rows back. So one row, updated in place, is enough:
Java
int[] row = new int[cols];
Arrays.fill(row, 1); // row 0: one way along the top edge
for (int r = 1; r < rows; r++) {
for (int c = 1; c < cols; c++) {
row[c] = row[c] + row[c - 1]; // row[c] is still "row r-1"; row[c-1] is already "row r"
}
}
return row[cols - 1];
Python
def unique_paths(rows: int, cols: int) -> int:
row = [1] * cols # row 0: one way along the top edge
for _ in range(1, rows):
for c in range(1, cols):
row[c] = row[c] + row[c - 1] # row[c] is still "row r-1"; row[c-1] is already "row r"
return row[cols - 1]
Look at row[c] + row[c - 1] as the loop moves left to right. row[c] hasn't been updated yet in this pass, so it still holds the value from the row above. row[c - 1] was just updated, so it holds the value to the left in the current row. One array plays both parts, and memory drops to O(cols).
Where you'll see it
Diff tools, spell checkers and DNA sequence alignment all fill a table like this. Each cell compares two prefixes, one of each string, and is built from three neighboring cells. Counting paths is the simplest member of that family.
Which tool for which job?
| You need | Use |
|---|---|
| Count paths moving right/down | dp[r][c] = dp[r-1][c] + dp[r][c-1] |
| Count paths, no obstacles, one number | the closed form C(rows + cols - 2, rows - 1) |
| Cheapest right/down path | grid[r][c] + min(up, left) |
| Only the final answer | one rolling row, O(cols) |
| The path itself, not just its cost | keep the full table and walk back |
| Moves in all four directions | Dijkstra (or BFS for equal costs) - not grid DP |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Edges initialized to 0 instead of 1 (counting) | every count is 0 or wrong | one way along each edge, until an obstacle |
| Filling in an order that reads unfilled cells | stale zeros flow through | top-to-bottom, left-to-right |
[[0] * cols] * rows in Python | every row is the same list | [[0] * cols for _ in range(rows)] |
An int path count in Java | overflows from an 18 x 18 grid | long (to 34 x 34), then modular or big integers |
| Grid DP when moves can go up or left | it misses cheaper paths | a shortest-path algorithm |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why do the first row and first column start at 1, not 0?
Show answer
There's exactly one way to reach a cell on the top or left edge: go straight along the edge. That's one real path. With 0 there, every cell that adds them in would come out too small, and in fact every count would be 0.
2. The table is filled column by column instead of row by row. Does it still work? Which order would break it?
Show answer
It still works. Column by column, the column to the left is finished and the cell above was filled just before. All a cell needs is that both of its inputs exist first. Filling bottom to top or right to left would break it: the cell above or to the left would still hold its default 0.
3. Why is one rolling row enough for the final answer?
Show answer
A cell depends only on the row directly above and on cells to its left in the same row. Once row r - 1 has been used to build row r, nothing needs it again. So one array, updated left to right, can hold both.
Key takeaways
- Each cell is built from cells already filled: here, the one above plus the one to the left.
- The edges need the right base case, 1 for counting paths. A 0 there spoils every cell after it.
- Fill in an order where both inputs exist first. Row by row, left to right is the simplest.
- If no cell looks back more than one row, one rolling row is enough: O(cols) memory.
- Minimum path sum and edit distance fill tables the same way, with a different combining rule and base case.