Unique paths with obstacles and math.comb in Python

Why this matters

A grid is a table of cells. Rows run across and columns run down. Many everyday problems look like this: a robot in a warehouse that can only move right or down, a street map with blocked roads, a seating plan with gaps. A common interview question asks how many routes lead from the top-left corner to the bottom-right corner when you may only move right or down. The question gets harder when some cells are walls and a route cannot pass through them.

This lesson solves the question two ways. The first way fills a table of counts, one cell at a time. It handles walls with one simple rule. The second way uses a formula from counting. It is fast, but it works only when there are no walls. Seeing exactly why the formula breaks when walls appear is the reason the table is needed.

The minimum path sum lesson later in this module uses the same kind of table, but it asks for the cheapest route instead of the number of routes.

Every program in this lesson is a plain Python file. The programs marked python run print their output without reading input. To run one on your own computer, save it as main.py and run python3 main.py. The outputs shown were produced on Python 3.14.

The problem

Think of the grid as a map. The robot starts in the top-left cell and must reach the bottom-right cell. Each move takes it one cell right or one cell down. Some cells are blocked, and the robot cannot enter them.

We number cells by row and column, starting from 0. The cell in row 0, column 0 is the top-left corner. The cell in row 2, column 1 is two rows down from the top and one column in from the left, and so on.

Take a 3 by 3 grid with no blocked cells. The robot needs exactly 2 moves down and 2 moves right to reach the far corner. Here R means a move right and D means a move down. The six possible routes are:

• RRDD
• RDRD
• RDDR
• DRRD
• DRDR
• DDRR

Each route is an ordering of the same four moves. Counting routes means counting these orderings. That idea becomes a formula later in the lesson.

Python words used in this lesson

• A list is an ordered row of values, written in square brackets, such as [1, 1, 1]. Its values are numbered from 0.
• A list of lists stores a grid. grid[1][2] means row 1, then column 2 inside that row.
• len(x) returns how many items a list has.
• A negative index counts from the end. row[-1] is the last item. The mistakes section shows why this matters.
• range(n) gives the numbers 0 up to n - 1.
• // divides and drops the remainder, so 7 // 2 is 3.

Step 1: Count small grids by hand

Start with a 2 by 2 grid. There are only two routes, RD and DR. The robot goes right then down, or down then right.

Now look at one cell in the middle of a bigger grid. Call it cell (r, c). The robot can arrive at this cell in only two ways. Its last move was either a move down from the cell above it, cell (r - 1, c), or a move right from the cell to its left, cell (r, c - 1). Nothing else can reach it, because the robot never moves up or left.

So the number of ways to reach cell (r, c) is:

• the number of ways to reach the cell above, plus
• the number of ways to reach the cell to the left.

This sum is the whole idea of the table. Each cell's count is built from the counts of two cells that come earlier in the walk. Cells on the top row have no cell above them, and cells on the left column have no cell to their left. Treat a missing neighbour as 0 ways.

The top-left cell is special. The robot starts there, so there is exactly 1 way to be at the start, the empty route.

Fill the table for the 3 by 3 grid. The top row is all 1s, because the robot can only move right along it, and that is one route per cell. The left column is also all 1s, for the same reason going down. Every other cell is the sum of the cell above and the cell to its left:

1 1 1
1 2 3
1 3 6

The bottom-right cell holds 6. That matches the six routes listed earlier.

Step 2: Add the rule for blocked cells

A blocked cell is simple. No route can enter it, so the number of ways to reach it is 0. The cells after it still get their counts from their neighbours, so a blocked cell passes its 0 along automatically. For example, if the cell above a cell is blocked and the cell to its left is open, the cell gets the count of the cell to its left and nothing from above.

The only special case is the start. If the top-left cell is blocked, there is no way to start, and the answer is 0.

Take a 3 by 3 grid with one blocked cell in the middle, at row 1, column 1. Its table is:

1 1 1
1 0 1
1 1 2

Check the bottom-right cell. It is the cell above it, row 1 column 2, which holds 1, plus the cell to its left, row 2 column 1, which holds 1. Together that is 2. Two routes survive: RRDD and DDRR. The routes RDRD, RDDR, DRRD and DRDR all pass through the middle cell.

Here is the full program. It builds the table with a function and prints it.

Output:

open 3x3: 6
[1, 1, 1]
[1, 2, 3]
[1, 3, 6]
blocked centre: 2
[1, 1, 1]
[1, 0, 1]
[1, 1, 2]
start blocked: 0

The first if in the loop is the blocked-cell rule. It comes first, so a blocked start cell gets 0 and never gets the value 1.

The line dp = [[0] * cols for _ in range(rows)] builds rows separate lists, and each one holds cols zeros. The _ is a name for a value the loop does not use. The mistakes section shows what goes wrong when each row is not built separately.

The lines with if i > 0 else 0 are Python's one-line form of an if and an else. value if condition else other gives value when the condition is true and other when it is false. When i is 0, the code uses 0 and never reads dp[-1].

dp[-1][-1] is the last row and the last column, which is the bottom-right cell.

Step 3: Keep one row instead of the whole table

Each cell reads only the cell above it and the cell to its left. Once a row is finished, the rows above it are never read again. That means the program can keep one row of counts and update it as it goes.

Read the update carefully. Before we change a slot in the row, that slot still holds the count from the row above. It is the cell above. The slot to its left has already been updated for the current row, so it holds the cell to the left. Going left to right makes both facts true at once:

row[j] = from_above + from_left

Here from_above is the old value in row[j], and from_left is the new value in row[j - 1]. The program below does this and prints the row after each pass. The print line uses an f-string, which is a string that starts with f and puts the value of each name inside curly braces.

Output:

after row 0: [1, 1, 1]
after row 1: [1, 0, 1]
after row 2: [1, 1, 2]
answer = 2

The printed rows match the full table from the previous step. The memory use drops from one list per row to one list in total. For a grid with a million rows, the full table holds a million lists, while this version holds one. The time is the same, because every cell is still visited once.

Step 4: The formula for an empty grid

When there are no blocked cells, a shortcut exists. Go back to the routes listed in the first step. Every route for a grid with R rows and C columns uses the same number of moves:

• it moves down exactly R - 1 times, and
• it moves right exactly C - 1 times.

The total number of moves is S = (R - 1) + (C - 1). A route is a choice of which of those S moves are downs. The other moves are rights. So counting routes means counting how many ways there are to pick the R - 1 down moves out of S moves.

Mathematicians write this as C(S, R - 1), read as "S choose R - 1". It is the number of ways to choose a fixed number of items from a larger set when the order of the choice does not matter. For the 3 by 3 grid, S is 4, and we pick 2 downs out of 4 moves. Look at the six routes again. Each one is one way to place the two Ds among four positions.

Here is the formula worked for 3 by 3:

• S = (3 - 1) + (3 - 1) = 4
• choose 2 downs out of 4 moves = C(4, 2) = 6

That matches the table.

How to compute C(n, k) step by step

The formula for choosing k items from n has a product form that is easy to compute:

C(n, k) = (n - k + 1)/1 times (n - k + 2)/2 times ... times n/k

In words, multiply the numbers from n - k + 1 up to n, dividing by 1, 2, and so on up to k. The trick is that after each step the running answer is still a whole number. The partial answer after step i is C(n - k + i, i). That makes the division exact at every step, so Python's // gives the exact answer with no rounding.

Try it for C(4, 2):

• Step 1: multiply by n - k + 1 = 3, divide by 1. Result 3.
• Step 2: multiply by n - k + 2 = 4, divide by 2. Result 6.

The program below uses this loop as the function choose. It also calls math.comb, which is in the standard library and does the same job. The math module ships with Python, so no install is needed. The check loop at the end compares the formula with the table.

Output:

choose(4, 2) = 6
math.comb(4, 2) = 6
3x3 formula = 6
3x7 formula = 28
formula matches DP for 1..12 by 1..12: True
20x20 formula = 35345263800
35x35 formula = 28453041475240576740
35x35 DP = 28453041475240576740
40x40 DP = 27217014869199032015600
40x40 formula = 27217014869199032015600

The check loop compares the formula with the table for every grid from 1 by 1 up to 12 by 12. It prints True. That is good evidence, but it is a test on 144 sizes and not a proof. The proof is the counting argument from the previous step.

Why the numbers get large

A 20 by 20 grid has about 35 billion routes. A 35 by 35 grid has about 28 quintillion routes.

In Java, a long holds whole numbers only up to 9,223,372,036,854,775,807. Past that limit it wraps around to a negative number without an error. Python whole numbers have no upper limit, so the table and the formula give exact answers for every size in this lesson. The program below shows the boundary of a 64-bit signed integer and what Python does one step past it.

Output:

largest signed 64-bit value: 9223372036854775807
one more: 9223372036854775808
2 ** 100 = 1267650600228229401496703205376

Past the limit, Python keeps the exact value. The 40 by 40 count has 23 digits, and both methods print the same exact value. Some problems ask for the answer modulo a number, which means the remainder after dividing by it. That is a different task and is not needed here.

Step 5: What the formula cannot do

The formula assumes every route is a free choice of downs and rights. A blocked cell breaks this assumption, because some of those choices run through the wall.

Look at the 3 by 3 grid with the blocked middle cell. The formula says 6 routes. The table says 2. The four missing routes are exactly the ones that pass through the middle cell. The formula does not know the wall is there, so it keeps counting them.

There are formulas that count around walls, but they add extra terms for each wall. The table handles any number of walls with the same single rule, so it is the simpler tool when walls exist. Use the formula only when you can be sure nothing is blocked.

Common mistakes

1. Forgetting that a blocked start cell is blocked

Here is a version that sets the start cell to 1 before the loop and then skips it:

Output:

buggy answer when start is blocked: 2

The correct answer is 0, because the robot cannot stand on a blocked start cell. This bug gives a plausible but wrong number, and it does not raise an error. Test the start cell and the end cell with a blocked grid every time you write this kind of code.

2. Reading index -1 without an error

In Java and many other languages, reading dp[i - 1] when i is 0 is an error. Python does not stop there. A negative index counts from the end of the list, so dp[-1] is the last row, and row[-1] is the last value in the row. The program keeps running and reads a value that has nothing to do with the cell above or to the left.

This version of the rolling method leaves out the j > 0 check:

Output:

no guard on an open 3x3 grid: 13

The correct answer is 6. For j = 0, the code reads row[-1], the last value in the row. That value still holds the count from the row above, so the first column gets counts that are too large, and the error spreads from there. The fix is to check i > 0 and j > 0 before each read, as the main program does.

3. Building rows that share one list

This is a trap that only shows up with lists of lists. The expression [[0] * cols] * rows makes rows references to the same list, not rows separate lists.

Output:

shared rows: [[0, 5, 0], [0, 5, 0], [0, 5, 0]]
separate rows: [[0, 0, 0], [0, 5, 0], [0, 0, 0]]
same object? True

Changing one cell changed the same column in every row, because the rows are one list. The is operator checks whether two names refer to the same object, and here it prints True. The table in build_table uses a list comprehension, a short loop written inside square brackets, which creates a new list for each row.

4. Using / instead of //

In Python, / always gives a float, which is a number stored with about 16 significant digits. Past about 9 quadrillion, which is 2 to the power 53, a float cannot store every whole number. The last digits are then wrong, and Python gives no warning.

Output:

choose_float(4, 2) = 6.0
choose_float(68, 34) = 2.845304147524058e+19
math.comb(68, 34) = 28453041475240576740
int(choose_float(68, 34)) = 28453041475240579072
exact? False

The float version is close but not exact, and its last four digits are wrong. Use // when the numbers are whole and the answer must be exact, as the choose function does.

5. Using the formula when a wall exists

The formula ignores walls. A program that calls unique_paths(3, 3) for a grid with a wall in the middle returns 6, but the correct answer is 2. Use the formula only when the grid is fully open. Use the table whenever a cell might be blocked.

Practice

Exercise 1: The top-right corner is blocked

Count the routes in a 2 by 2 grid where the top-right cell, row 0 column 1, is blocked. Use the table method.

Show the answer

The answer is 1. The top-right cell holds 0. The bottom-left cell holds 1, from the top-left cell. The bottom-right cell is the cell above it, which is 0, plus the cell to its left, which is 1. The only surviving route is DR, down then right.

Exercise 2: Fill a 3 by 4 table with one wall

Fill the table for a grid with 3 rows and 4 columns. The cell at row 1, column 2 is blocked. Give the final answer.

Show the answer

The table is:

1 1 1 1
1 2 0 1
1 3 3 4

The final answer is 4. Passing this grid to build_table from step 2 returns the same table.

Exercise 3: A 5 by 5 grid with no walls

Use the formula to count the routes in a 5 by 5 grid with no blocked cells.

Show the answer

The number of moves is S = (5 - 1) + (5 - 1) = 8. Each route has 4 downs. The count is C(8, 4) = 70. In Python, math.comb(8, 4) returns 70.

Exercise 4: A single row with a wall

Count the routes in a 1 by 5 grid, one row with five cells, where column 2 is blocked.

Show the answer

The answer is 0. A route on a single row can only move right, so it must pass column 2. The table gives 0 for the last cell.

Exercise 5: The largest square grid that fits in a 64-bit integer

For a square grid of n by n cells with no walls, find the largest n whose route count fits in a signed 64-bit integer. That is the largest value of 2**63 - 1, which is 9,223,372,036,854,775,807, the limit of a Java long.

Show the answer

The answer is n = 34. Its count is 7219428434016265740, which is below the limit. The count for 35 by 35 is 28453041475240576740, which is too large. A loop that tries n = 1, 2, 3 and so on, using math.comb, and stops at the first n whose count is above the limit finds 35, so the answer is one less.

Summary

• A cell's route count is the count of the cell above plus the count of the cell to its left.
• A blocked cell has count 0, and the top-left cell has count 1 when it is open.
• One row of counts is enough, because each cell reads only the row above and the cell to its left.
• With no blocked cells, the count is math.comb(S, R - 1), where S is the total number of moves.
• The formula ignores walls, so it gives a wrong answer whenever a cell is blocked.
• Python whole numbers have no size limit, so the counts stay exact, but / turns them into floats and loses digits.