How do you count the number of unique paths through a grid where you may only move right or down?
You fill in a table where each cell holds the number of ways to reach that cell, and each cell is the sum of the cell above it and the cell to the left.
def unique_paths(rows, cols):
table = [[1] * cols for _ in range(rows)]
for r in range(1, rows):
for c in range(1, cols):
table[r][c] = table[r - 1][c] + table[r][c - 1]
return table[rows - 1][cols - 1]
So how does it work? The first row and the first column are all ones, because there is exactly one way to reach any cell in them. You can only come from one side, so you have no choice to make.
And then every other cell is the sum of the two cells that you can come from, which are the one above and the one to the left. The paths that come from above and the paths that come from the left are different paths, so you add the counts.
the grid is 3 by 3
the table
1 1 1
1 2 3
1 3 6
the answer is 6
And there is a shortcut that is worth knowing about. The number of paths is a combination. You have to make rows minus one moves down and cols minus one moves right, in some order, so the answer is the number of ways of choosing where the down moves go.
import math
def unique_paths_formula(rows, cols):
return math.comb(rows + cols - 2, rows - 1)
And that formula is O of 1 in the number of steps, but it works with big numbers that grow very fast. The table version is the one to write in an interview, because it shows the way of thinking.
And the complexity is O of rows times cols for the time, and the same for the space. And you can get the space down to O of cols by keeping one row, the same trick as the edit distance.
So the rule to remember is this. The first row and the first column are ones, and every other cell is the sum of the two before it.
The last question in this topic shows the version with blocked cells.