Dynamic Programming · 077Medium
Unique Paths
A robot starts at the top-left of an m x n grid and may only move right or down. Return the number of distinct paths to the bottom-right corner.
Constraints
- 1 <= m, n <= 100
- The answer is guaranteed to be at most 2 * 10^9.
Examples
uniquePaths(3, 7) -> 28 uniquePaths(3, 2) -> 3 uniquePaths(1, 1) -> 1 uniquePaths(1, 10) -> 1 // a single row uniquePaths(2, 2) -> 2 // right-down or down-right uniquePaths(10, 10) -> 48620
Edge cases
- A single row or column has exactly one path.
Show the target complexity (spoiler)
- Naive
- O(2^(m+n)) time — recurse on both moves without memoisation.
- Target
- O(m * n) time, O(n) space — dp[i][j] = dp[i-1][j] + dp[i][j-1], reducible to a single rolling row.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/077-unique-paths.js ./practice c 077