DSA problem
Unique Paths
A robot is located at the top-left corner of an m x n grid. It can move only down or right at any step and wants to reach the bottom-right corner. Return the number of unique paths it can take.
This is the canonical grid-DP setup. To stand on any cell (i, j) the robot must have come from either the cell directly above (i - 1, j) or the cell directly to its left (i, j - 1). So the number of paths ending at (i, j) equals the sum of paths ending at those two cells, with the boundary condition that the first row and first column each have exactly one path (you simply walk straight).
A closed-form binomial-coefficient answer exists — the count is C(m + n - 2, m - 1) because every path is a sequence of m - 1 downs and n - 1 rights — but it requires either big integers or very careful multiplication. The DP formulation is more flexible, generalizes to obstacle variants, and is the right mental model for grid problems in general.
The optimal DP fills a 2D table in row-major order in O(m * n) time. Because each row only depends on the row above, the space can be compressed to a single 1-D array of length n: walk left to right and update dp[j] += dp[j - 1]. After processing all m rows the answer sits in dp[n - 1]. This runs in O(m * n) time using O(n) space — the textbook 2D-DP-to-1D space optimization.
Examples
m = 3, n = 728m = 3, n = 23m = 1, n = 11Constraints
- 1 <= m, n <= 100
- The answer is guaranteed to fit in a 32-bit signed integer for the given range.
- The robot moves only right or down at each step.
- The robot starts at `(0, 0)` and must reach `(m - 1, n - 1)`.
- No cell is blocked in this version of the problem.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.