Paths through a grid

A floor-cleaning robot starts on the top-left cell of a grid of floor tiles, and it knows only two moves: one cell right or one cell down. Count the different routes that bring it to the bottom-right cell. The backtracking module counted paths by walking every one of them, which takes as long as there are paths, and a 20 × 20 grid has over 35 billion right-and-down paths. DP counts them without walking any.

Every route into a cell ends with a last move, and there are only two kinds: down out of the cell above, or right out of the cell to the left. No route is of both kinds, so the count for a cell is the two counts added up:

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

A cell on the top row is reached only by moving right all the way, and a cell in the left column only by moving down all the way: one route each. Go through the rows from the top, and through each row from the left, and both cells a count needs are finished before it:

rows, cols = 3, 5
paths = [[0] * cols for _ in range(rows)]
for r in range(rows):
    for c in range(cols):
        if r == 0 or c == 0:
            paths[r][c] = 1                                   # along an edge
        else:
            paths[r][c] = paths[r - 1][c] + paths[r][c - 1]   # above + left
for row in paths:
    print(row)

[1, 1, 1, 1, 1]
[1, 2, 3, 4, 5]
[1, 3, 6, 10, 15]

The bottom-right cell says 15. Each cell takes one addition, so a grid of rows × cols cells costs O(rows × cols) time and memory: 400 additions for the 20 × 20 grid, instead of 35 billion paths.

A table of lists: the trap

The table is built with [[0] * cols for _ in range(rows)], a new list for every row. The shorter [[0] * cols] * rows looks the same, but it isn't. * repeats the reference to one inner list, so every row is the same list, as the references module showed:

>>> table = [[0] * 3] * 2
>>> table[0][0] = 7
>>> table
[[7, 0, 0], [7, 0, 0]]
>>> table = [[0] * 3 for _ in range(2)]
>>> table[0][0] = 7
>>> table
[[7, 0, 0], [0, 0, 0]]

[0] * 3 on its own is fine: a number can't be changed in place, so sharing it does no harm. A list of lists needs the comprehension.

Walls

Now some cells hold furniture, #, and the robot can't drive onto them. Such a wall cell gets 0 routes. Watch the edges: along the top row, the only way in is from the left, so one wall there cuts off the rest of that row, and the left column works the same way going down. Rather than writing those rules out, add up only the neighbors that exist:

def count_paths(grid):
    rows, cols = len(grid), len(grid[0])
    paths = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "#":
                continue                              # a wall: 0 paths
            if r == 0 and c == 0:
                paths[r][c] = 1
            else:
                above = paths[r - 1][c] if r > 0 else 0
                left = paths[r][c - 1] if c > 0 else 0
                paths[r][c] = above + left
    return paths[rows - 1][cols - 1]


print(count_paths([".....",
                   "..#..",
                   "....."]))
print(count_paths(["...#.",
                   ".....",
                   "....."]))

6
12

The open 3 × 5 grid had 15 routes. In the first grid, the 9 that pass through the middle cell are gone. In the second, the 3 routes through the wall are gone, and the top-right cell is cut off with them: the only way into it was from the left, through the wall, so it gets 0 routes.

The cheapest path

Now each cell has a cost, and you want the right-and-down path from corner to corner with the smallest total cost, both corners included. The same table works with another rule: the cheapest way into a cell comes from the cheaper of its two neighbors, so

best[r][c] = cost[r][c] + min(best[r - 1][c], best[r][c - 1])

On the top row there's only the neighbor on the left, and in the left column only the one above. Trying every path instead takes as long as there are paths: exponential again.

Each row of these tables reads only the row above it, so, as with the stairs, you could keep a single row and update it in place, for O(cols) memory. Keep the whole table when you want to read it afterward, for instance to find the path itself.