Unique Paths

Medium#622d table

A robot stands in the top-left corner of a grid with m rows and n columns and has to reach the bottom-right corner. It can only step right or down. Count the different routes it can take. Our example: a 3 × 4 grid, 10 paths.

62 Unique PathsWalkthrough · 1×

Example: a 3 × 4 grid. Watch the last cell: 4 paths arrive from above and 6 from the left, and they add up to the answer.

0123012
emptypaths into this cellthis stepread fromanswer

An empty table: 3 rows, 4 columns, one cell per square of the grid

01/28
restart · back · play · step
Speed
1function uniquePaths(m, n):
2 dp = table of m rows and n columns
3 for c from 0 to n - 1:
4 dp[0][c] = 1 // the top row: only moves right
5 for r from 1 to m - 1:
6 dp[r][0] = 1 // the left column: only moves down
7 for c from 1 to n - 1:
8 up = dp[r - 1][c]
9 left = dp[r][c - 1]
10 dp[r][c] = up + left
11 return dp[m - 1][n - 1]
state
dp
[[–, –, –, –], [–, –, –, –], [–, –, –, –]]
r
–
c
–
up
–
left
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every path into (r, c) makes its last move either down from (r - 1, c) or right from (r, c - 1). No path does both, so the paths into a cell are exactly the paths into those two cells, added up.
  2. A cell of the top row or the left column has only one way in, a straight line from the start, so it holds 1. These cells start the table.
  3. Row by row, left to right, both cells a cell reads are filled before it, so every cell is computed once from finished numbers.

Complexity

Time O(m × n): each cell is one addition. Memory O(m × n) for the table; a cell reads only its own row and the row above, so one row of n cells is enough.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.