Unique Paths

Problem

A robot stands in the top-left cell of an m x n grid and wants to reach the bottom-right cell. At each step it may move only one cell right or one cell down. Return the number of distinct routes from the start to the destination.

• Grid dimensions are small enough to fit comfortably in memory, up to a few hundred rows and columns.
• The returned count fits in a 32-bit signed integer.

Examples

• m = 4, n = 5 → 35. Every route uses 3 down-moves and 4 right-moves in some order.
• m = 2, n = 3 → 3. The routes are RRD, RDR, DRR.
• m = 1, n = 6 → 1. A single row leaves only one way through: straight right.

Hints

1. How many ways are there to reach a cell if you already know how many ways reach the cell above it and the cell to its left?
2. Every cell in the first row and first column can be reached in exactly one way. Build outward from there.
3. Bottom-up 2D DP, or notice that any route is a fixed number of D and R moves and count arrangements with a binomial coefficient.