Unique Paths

Problem A robot on an m x n grid starts top-left and moves only right or down. Count the unique paths to the bottom-right.

Input / Output

• Input: ints m, n. Output: number of paths.

Constraints

• 1 <= m, n <= 100; answer fits in a signed 32-bit int per classic constraints.

Example

• m = 3, n = 7 → 28; m = 3, n = 2 → 3.

Expected approach

• DP: paths(i,j) = paths(i−1,j) + paths(i,j−1), edges = 1; O(m*n) time, O(n) rolling space. Closed form: C(m+n−2, m−1) — every path is a choice of which of the m+n−2 moves are downs; compute multiplicatively to avoid overflow. Giving both and knowing when combinatorics breaks (obstacles → Unique Paths II) is the complete answer.