Example 1
ready- Input
m = 3 n = 7- Expected
28- Why
- 28 right-and-down move sequences reach the far corner
Unique Paths
35 min · uniquePaths()mediumOpen in LeetCode #62 ↗
A delivery robot has only two controls: right and down. Even on a modest grid, those two buttons can produce a surprising number of routes.
The robot starts in the top-left cell of an m by n grid. It wants to reach the
bottom-right cell, moving exactly one cell right or one cell down at each step. Return
the number of distinct paths it can take.
A few ground rules:
mis the number of rows andnis the number of columns.- The robot stays inside the grid.
- Two paths are different when their sequences of moves differ.
Constraints
1 <= m, n <= 20- The exact path count is less than
2^31.
Hints
Ask how a cell is entered
Except along the top and left edges, a robot can enter a cell from exactly two places: the cell above it or the cell to its left.
Turn that into a rule
If ways[row][col] counts paths into one cell, then it equals the paths into the
cell above plus the paths into the cell on the left.
Keep only yesterday's row
While updating one row from left to right, dp[col] still holds the value from
above and dp[col - 1] already holds the new value from the left. One row is enough.
Follow-up
Can you derive the same answer by choosing where the down moves appear among all moves, without building a grid at all?
Visible cases
Examples
Example 2
ready- Input
m = 3 n = 2- Expected
3- Why
- the single right move can appear before, between, or after the two down moves
Example 3
ready- Input
m = 1 n = 1- Expected
1- Why
- the robot is already at its destination
Interview signal
Asked at
AmazonGoogleBloomberg
Full-grid DP — count paths into every cell
Dynamic programming (DP) stores answers to smaller subproblems so later answers can
reuse them. Let ways[row][col] hold the number of routes into one cell. The top row and
left column each have one route: keep moving straight from the start.
Every other cell follows a transition — the rule that builds one DP answer from smaller answers:
ways[row][col] = ways[row - 1][col] + ways[row][col - 1]
def unique_paths(m: int, n: int) -> int:
ways = [[1] * n for _ in range(m)]
for row in range(1, m):
for col in range(1, n):
ways[row][col] = ways[row - 1][col] + ways[row][col - 1]
return ways[m - 1][n - 1]By the time you fill a cell, both values it depends on are ready. Time O(mn). Space O(mn) for the table.
One-row rolling DP — keep only what the transition reads
The transition never looks two rows back. In a single array, dp[col] begins an update
as the answer from above; dp[col - 1] is already the answer from the left. Add them and
the same slot becomes the answer for the current cell.
def unique_paths(m: int, n: int) -> int:
dp = [1] * n
for _ in range(1, m):
for col in range(1, n):
dp[col] += dp[col - 1]
return dp[n - 1]The rolling DP uses the same transition, just with storage reused after each row. Time O(mn). Space O(n) for the one-row array.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
28
Run: visible + custom · Submit: full suite