Unique Paths

Every path into a cell must arrive from the cell above it or the cell to its left, so the number of paths to a cell is the sum of the paths to those two cells. Fill the grid from the top left corner and read the answer from the bottom right.

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]


print(unique_paths(3, 7))
print(unique_paths(3, 2))

The outputs are 28 and 3. A three by seven grid has twenty eight routes and a three by two grid has three.

The mechanism is the additive recurrence. The first row and the first column are seeded with one, because there is exactly one way to travel along the top edge or down the left edge. Every interior cell then accumulates the two contributions, and because the fill order respects the dependencies, every cell is correct by the time it is used.

The trade-off to name is that the table costs space quadratic in the product of the dimensions, when only the last row is really needed, since each row depends only on the row above it. The rolling array version uses linear space and is the one to reach for when the grid is large. The other point is the closed form: the answer is a binomial coefficient, and computing it directly is faster than filling a table, though the table version is what you should write in an interview because it is much easier to verify.

A blocked cell has zero paths through it, so you set its table entry to zero and skip the usual update. Every other cell keeps the same recurrence, and the blocked cells act as holes that the paths must route around.

def unique_paths_with_blocks(grid):
    rows, cols = len(grid), len(grid[0])
    table = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                continue
            if r == 0 or c == 0:
                table[r][c] = 1
            else:
                table[r][c] = table[r - 1][c] + table[r][c - 1]
    return table[rows - 1][cols - 1]


grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
print(unique_paths_with_blocks(grid))

The output is 2. With the middle cell blocked, the two routes around it are the only ones left, and the four routes that existed in an open grid are gone.

The mechanism is that the blocked cell contributes zero to both the cell below it and the cell to its right, so any path that would have gone through it simply is not counted. The edge case is a blocked cell on the first row or column, where the base value of one has to be suppressed, otherwise the seeding would claim that a path exists along an edge that is blocked.

The trade-off to name is the same as in the unblocked version, quadratic space for the table against linear space for the rolling version, and the time is linear in the number of cells. The other point is that the answer can be zero, which is different from the unblocked case where a path always exists, and that is worth checking explicitly rather than assuming the grid is passable.