Unique Grid Paths
Hard · rating 1500 · dp, combinatorics
Read two integers m and n. A robot starts at the top-left of an m × n grid and can move only right or down. Print the number of distinct paths to the bottom-right.
Constraints: 1 ≤ m, n ≤ 20
Editorial
Unique Paths is a classic grid dynamic-programming (and combinatorics) interview problem: a robot at the top-left of an m×n grid moving only right or down — how many distinct paths reach the bottom-right?
DP approach
Each cell is reachable only from the cell above or to its left, so paths[i][j] = paths[i-1][j] + paths[i][j-1], with the first row and column all 1.
Combinatorial shortcut
Every path makes exactly m-1 downs and n-1 rights in some order, so the answer is the binomial coefficient C(m+n-2, m-1).
from math import comb
return comb(m + n - 2, m - 1)Complexity
DP: O(m × n) time. Combinatorial: O(min(m, n)) time, O(1) space.