532. 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).

Constraints - `1 ≤ m ≤ 100` - `1 ≤ n ≤ 100`