Easy Problemscountinggrid

Count all paths in a Grid

Given a grid, and starting at its top-left corner while moving only right or down at each step, count the number of distinct paths to the bottom-right corner.

Do this lesson first: climbing stairs

Example input

a grid with 6 rows and 4 columns

Expected output

56

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Ask what the last step onto (r, c) was. It was either a step down from (r - 1, c) or a step right from (r, c - 1). Those two sets of routes can never overlap, because they differ in their final step, and between them they are every route that arrives here at all. So the count is the sum of the two, not a choice between them. min-cost-path asks this same question about these same two neighbours and takes a min instead, because there the routes compete on price; here they are all counted.

dp[0][0] = 1: standing on the start is one route, the empty one. Every other cell of row 0 and of column 0 is 1 as well, and those are worth declaring out loud rather than deriving: a cell in the top row has no cell above it to come from, so the only route into it is the single straight run of steps right, and the first column is the same story with steps down. Filling row-major, left to right within each row, means the cell above and the cell to the left already hold their final counts before any cell uses them, which is the only ordering property the recurrence needs. This grid keeps its 6 rows fixed and lets the slider change the number of columns, so you can watch the table get wider one column at a time while its row count, and with it the number of downward steps every route has to take, stays put.

Tabulation over every cell, since every cell of the grid sits on some route towards the corner and will be needed. This is also the rare problem whose table you can throw away entirely: a cell reads only the row above and its own left neighbour, so one rolling row of length cols is enough, and on top of that the answer has a closed form, C((rows - 1) + (cols - 1), rows - 1), because a route is nothing but an ordering of downs and rights. Keep the table anyway, because it is the same row-major sweep over the same state with the same two dependencies as min-cost-path and paths-in-a-grid-with-obstacles. The only thing that changes across those three pages is what a cell does with the two values it takes in.

Time O(rows × cols)Space O(rows × cols), reducible to O(cols) with one rolling row, or O(1) via the closed form

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0][0] = 1: standing on the start is one route, the empty one. Every other cell of row 0 and of column 0 is 1 as well, and those are worth declaring out loud rather than deriving: a cell in the top row has no cell above it to come from, so the only route into it is the single straight run of steps right, and the first column is the same story with steps down. Filling row-major, left to right within each row, means the cell above and the cell to the left already hold their final counts before any cell uses them, which is the only ordering property the recurrence needs. This grid keeps its 6 rows fixed and lets the slider change the number of columns, so you can watch the table get wider one column at a time while its row count, and with it the number of downward steps every route has to take, stays put.

row r

0

1

2

3

0

1

2

3

4

2

1

3

6

10

3

1

4

10

20

4

1

5

15

35

5

1

6

21

56

column c: routes reaching (r, c)

count-all-paths-in-a-grid.ts

1function countPaths(rows, cols) {
2 const dp = Array.from({ length: rows }, () => new Array(cols).fill(1));
3 for (let r = 1; r < rows; r++) {
4 for (let c = 1; c < cols; c++) {
5 dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
6 }
7 }
8 return dp[rows - 1][cols - 1];
9}

Base caseComputedBeing readAnswer

The code, the trap, the variations

count-all-paths-in-a-grid.ts

1function countPaths(rows, cols) {
2 const dp = Array.from({ length: rows }, () => new Array(cols).fill(1));
3 for (let r = 1; r < rows; r++) {
4 for (let c = 1; c < cols; c++) {
5 dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
6 }
7 }
8 return dp[rows - 1][cols - 1];
9}

Where people go wrong

Counting steps rather than orderings, and then getting the closed form off by one. Every route across a 6 by 4 grid takes exactly 5 + 3 = 8 steps, so there is nothing here to optimize and no route is shorter than another; the only question is how many orders those 8 steps can come in. And both numbers in the closed form count steps rather than rows and columns: the top is the total number of steps, (rows - 1) + (cols - 1), and the bottom is how many of those steps go in one chosen direction. A 6 by 4 grid takes 5 downs and 3 rights, so it is C(8, 5) = 56, never C(10, 6) and never C(5, 3). The table is the safer place to start precisely because it never asks you to get that right.

Block some cells so that no route may stand on them.
Row 0 and column 0 stop being all 1s, because one obstacle in an edge makes every cell after it along that edge unreachable, so the bases shrink to the single start cell and the recurrence gains one rule: a blocked cell holds 0 no matter what its neighbours hold. That is paths-in-a-grid-with-obstacles, and nothing else about the sweep moves.
Allow diagonal moves as well as right and down.
A third term, dp[r - 1][c - 1], joins the sum. The closed form is gone, since routes no longer all have the same length, and the table becomes the only reasonable way to count them; those counts are the Delannoy numbers.
Count only the routes that pass through one particular cell.
Multiply the count of routes into that cell by the count of routes from it to the corner, which is this same table run from the other end. The recurrence never changes; the multiplication happens outside it.

Longest Common Substring Paths in a Grid with Obstacles