Dynamic programming · routine

Paths through a grid

From the top-left corner of a rows × cols grid, moving only right or down, how many different paths reach the bottom-right corner? Write grid_paths(rows, cols).

Every square is reached from the one above or the one to the left: its count is the sum of theirs. Fill the table row by row.

right answers
arguments left as they should be
fast enough at scale
without comb, factorial, math, lru_cache, cache, functools

def grid_paths(rows, cols):
    if rows == 1 or cols == 1:
        return 1
    return grid_paths(rows - 1, cols) + grid_paths(rows, cols - 1)

Run adds print(grid_paths(3, 7)) after your code, to try it.

Stuck on the idea rather than the code? The Tables and choices lesson walks through it.