Count grid paths from bottom-left to bottom-right

A grid has m rows (row 0 at the top) and n columns. You start in the bottom-left cell (m-1, 0) and must reach the bottom-right cell (m-1, n-1). Every move goes one column to the right, either up a row, on the same row or down a row, and must stay inside the grid. There are no obstacles. Count the distinct paths.

Interface

Unless you agree on a different interface with the interviewer, assume:

• count_paths(m: int, n: int) -> int — the number of paths from (m-1, 0) to (m-1, n-1). From (r, c) you may go to (r-1, c+1), (r, c+1) or (r+1, c+1).

Example

count_paths(3, 3)  ->  2     # straight along the bottom, or up-right then down-right
count_paths(3, 4)  ->  4
count_paths(4, 5)  ->  9
count_paths(1, 5)  ->  1     # one row: only straight moves
count_paths(3, 1)  ->  1     # start and end are the same cell

Constraints

• 1 <= m, n; the answer fits in a 64-bit integer, or return it modulo 10^9 + 7 if you say so first.

Clarifying questions

• Does a 1-column grid count as one path?
• Should the answer be exact or taken modulo a prime?
• Can I assume no blocked cells?

What a strong answer covers

• The recurrence: ways(r, c) = ways(r-1, c-1) + ways(r, c-1) + ways(r+1, c-1), filled column by column, with ways(m-1, 0) = 1.
• First an O(m·n) time and space table, then one column of O(m) space, because each column depends only on the previous one.
• Why the space cut is safe: build the new column into a fresh array, not in place, or the up and down neighbours get overwritten.
• Edge cases m = 1 and n = 1; small cases checked by hand.

Follow-ups

• Some cells are blocked.
• The start and end cells are arbitrary.
• n is huge but m is small: raise the m x m transition matrix to a power.