algorithmpro

Dynamic programming: grid paths

Count the paths across a grid that only move right or down.

time: O(n·m)
space: O(n·m)

// step through it

step 1 / 8

1function uniquePaths(m, n) {2  const dp = Array.from({ length: m }, () => new Array(n).fill(1));3  for (let r = 1; r < m; r++) {4    for (let c = 1; c < n; c++) {5      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];6    }7  }8  return dp[m - 1][n - 1];9}

	0	1	2	3
0	1	1	1	1
1	1
2	1

Make a 3 × 4 table. Every cell in the top row and the left column has exactly 1 path.

Tip: use the arrow keys to step.

// pro lesson

Unlock the full walkthrough

This lesson is part of Pro. Pro unlocks every step of every lesson, plus pattern drills and mastery insights.

See pricing

How it works

You can only enter a cell from the cell above it or the cell to its left. So the paths to a cell are the paths to the cell above plus the paths to the cell on the left. Every cell in the top row and left column has exactly one path. Fill the table row by row and the bottom-right cell holds the answer. Each cell is computed once: O(n·m) time and space.

Practice spotting this pattern →