How Many Ways Across
A robot starts at the top-left corner of an m by n grid and must reach the
bottom-right corner, moving only RIGHT or DOWN. Count the distinct paths.
Print the count modulo 1000000007.
3 x 7 -> 28
3 x 2 -> 3
1 x 5 -> 1 only one path when there is a single row
## The recurrence
Every path arrives at a cell either from above or from the left, and those two families are disjoint, because the last move is one or the other and never both:
ways[0][0] = 1
ways[r][c] = ways[r-1][c] + ways[r][c-1]
with missing neighbours contributing 0.
Partitioning by the LAST MOVE is what makes the sum a correct count rather than an overcount, and it is the same argument as counting by right endpoint in problem 475.
## Rolling the table down to one row
ways[r][c] reads only the row above and the cell to its left. So a single array suffices:
dp = [1] * n
for r in 1..m-1:
for c in 1..n-1:
dp[c] += dp[c-1]
When dp[c] += dp[c-1] runs, dp[c] still holds the value from the previous ROW and
dp[c-1] has already been updated for the CURRENT row. Those are exactly the two terms the
recurrence wants, so the in-place update is not a shortcut, it is the recurrence.
Initialising the whole array to 1 encodes the first row, where there is exactly one path to every cell.
## Two boundaries
1 x 5 and 5 x 1 both answer 1. A single row or column leaves no choice at all, and
these are the inputs that catch a loop starting at the wrong index.
1 x 1 answers 1: the robot is already at the destination and the empty path counts.
## The closed form, and why the table is still worth writing
Every path makes exactly m-1 down moves and n-1 right moves in some order, so the count
is C(m+n-2, m-1).
That is faster, and it stops generalising the moment the grid gains obstacles, which is problem 533. The table survives that change and the formula does not, which is the usual reason to prefer it.
## Cost
Time O(m n). Space O(n).