AlgoViz
HomeDynamic Programming

Grid Unique Paths : DP on Grids

Medium

Paths in = paths from above + paths from the left

Problem

Count the paths from the top-left to bottom-right of an m x n grid moving only right or down.

In simple words

Paths to a cell = paths from the cell above plus paths from the cell to the left.

The idea

Every cell is reached only from above or from the left, so its path count is the sum of those two. Filling the grid row by row gives O(m·n), and one row of storage is enough.

The trick

  • First row and first column are all 1 — a single route each.
  • The closed form is the binomial coefficient C(m+n-2, m-1).
  • One rolling row reduces space to O(n).
1
1
1
1
1
1
1
1
1

Step 1 of 6. Top row and left column have exactly 1 path. Every other cell = paths from above + from the left.

1/6
Optimal
timeO(n·m)spaceO(m)

Row-rolling sums.

1const row = Array(n).fill(1);2for (let i = 1; i < m; i++)3  for (let j = 1; j < n; j++)4    row[j] += row[j - 1];5return row[n - 1];

Input

grid
3 × 3

Memory

at
—
cells marked
5

Output

paths
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
m = 3, n = 7
Output:
28
Explanation:
28 distinct right/down routes across the grid.

Example 2

Input:
m = 3, n = 2
Output:
3
Explanation:
3 ways down a 3x2 grid.

Example 3

Input:
m = 1, n = 5
Output:
1
Explanation:
One straight row → a single path.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.