DSA Tracker

Visualize

Unique Paths

dp[cell] = dp[above] + dp[left]

time O(m*n)space O(m*n)

Every path to a cell arrives either from directly above or directly to the left — there's no other way in, since only right/down moves are allowed. So the number of ways to reach any cell is just the sum of the ways to reach those two neighbors, and the top row / left column are trivially 1 (a single straight line gets there). Filling the grid this way builds every answer from ones already computed.

Details

Animated on: 3x3 grid, top-left to bottom-right, moving only right or down — count the distinct paths.

Problem:Unique PathsMedium

dp[cell] = dp[above] + dp[left]

step 1 / 11

0
[0]
0
[1]
0
[2]
0
[3]
0
[4]
0
[5]
0
[6]
0
[7]
0
[8]

3x3 grid, flattened row-major. Only right/down moves are allowed, so the number of ways to reach a cell is just the sum of ways to reach the cell above and the cell to its left.

Pseudocode
1FUNCTION uniquePaths(m, n):
2  dp = an m by n grid
3  FOR each cell (i, j) in the grid:
4    IF i is 0 or j is 0: dp[i][j] = 1   (top row / left column)
5    ELSE: dp[i][j] = dp[i-1][j] + dp[i][j-1]   (from above + from left)
6  RETURN dp[m-1][n-1]

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 3x3 grid, flattened row-major. Only right/down moves are allowed, so the number of ways to reach a cell is just the sum of ways to reach the cell above and the cell to its left.
  2. (0,0) is on the top row or left column — only one way to reach it (a straight line). dp=1.
  3. (0,1) is on the top row or left column — only one way to reach it (a straight line). dp=1.
  4. (0,2) is on the top row or left column — only one way to reach it (a straight line). dp=1.
  5. (1,0) is on the top row or left column — only one way to reach it (a straight line). dp=1.
  6. (1,1): dp = up(1) + left(1) = 2.
  7. (1,2): dp = up(1) + left(2) = 3.
  8. (2,0) is on the top row or left column — only one way to reach it (a straight line). dp=1.
  9. (2,1): dp = up(2) + left(1) = 3.
  10. (2,2): dp = up(3) + left(3) = 6.
  11. Bottom-right corner dp[2][2] = 6 — the total number of distinct paths.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Unique Paths in the editorAll Dynamic Programming problemsBack to roadmap