Unique Paths
Medium · 2-D Dynamic Programming · Math · Dynamic Programming · Combinatorics
Problem
A robot starts at the top-left of an m x n grid and must reach the bottom-right. It may only move right or down.
Return how many distinct paths exist.
Examples
Input: m = 3, n = 7 Output: 28
Input: m = 3, n = 2 Output: 3
Right-Down-Down, Down-Right-Down, Down-Down-Right.
Constraints
- 1 <= m, n <= 100
- The answer is at most 2 * 10^9
Approaches
- Combinatorics — choose the down-moves — time O(min(m, n)), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
