DSA Tracker

Visualize

Unique Paths (DP on Grid)

dp[r][c] = dp[r-1][c] + dp[r][c-1]

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

A cell can only be entered from directly above or directly to its left — those are the only two moves allowed. Every path that reaches either neighbor extends into a distinct path through this cell, so the count here is just the sum of the counts at those two neighbors. The top row and left column each have only one possible route in, so they start at 1 and every interior cell builds on already-known neighbors.

Details

Animated on: m = 3, n = 3 — a robot starts top-left and can only move down or right; count the distinct paths to the bottom-right corner.

Problem:Unique Paths (DP on Grid)Medium

dp[r][c] = dp[r-1][c] + dp[r][c-1]

step 1 / 11

dp[r][c] = dp[r-1][c] + dp[r][c-1] — paths arrive only from above or from the left

A 3x3 grid. The robot only ever moves down or right, so the number of ways to reach a cell is the sum of the ways to reach the cell above it and the cell to its left.

Pseudocode
1FUNCTION countPaths(m, n):
2  dp[0][0] <- 1
3  FOR c FROM 1 TO n-1:
4    dp[0][c] <- dp[0][c-1]
5  FOR r FROM 1 TO m-1:
6    dp[r][0] <- dp[r-1][0]
7  FOR r FROM 1 TO m-1:
8    FOR c FROM 1 TO n-1:
9      dp[r][c] <- dp[r-1][c] + dp[r][c-1]
10  RETURN dp[m-1][n-1]

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. A 3x3 grid. The robot only ever moves down or right, so the number of ways to reach a cell is the sum of the ways to reach the cell above it and the cell to its left.
  2. The start cell (0,0) has exactly 1 way to be "reached" — staying put. dp[0][0] = 1.
  3. Top row: (0,1) can only be entered from the left, so it inherits that count unchanged. dp[0][1] = 1.
  4. Top row: (0,2) can only be entered from the left, so it inherits that count unchanged. dp[0][2] = 1.
  5. Left column: (1,0) can only be entered from above, so it inherits that count unchanged. dp[1][0] = 1.
  6. Left column: (2,0) can only be entered from above, so it inherits that count unchanged. dp[2][0] = 1.
  7. (1,1) is entered from above(1) or from the left(1) — every path through either neighbor is a distinct route here, so they add: dp[1][1] = 1 + 1 = 2.
  8. (1,2) is entered from above(1) or from the left(2) — every path through either neighbor is a distinct route here, so they add: dp[1][2] = 1 + 2 = 3.
  9. (2,1) is entered from above(2) or from the left(1) — every path through either neighbor is a distinct route here, so they add: dp[2][1] = 2 + 1 = 3.
  10. (2,2) is entered from above(3) or from the left(3) — every path through either neighbor is a distinct route here, so they add: dp[2][2] = 3 + 3 = 6.
  11. dp[2][2] = 6 — that many distinct paths lead from the top-left to the bottom-right corner.

Now solve it yourself

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

Solve Unique Paths (DP on Grid) in the editorAll Dynamic Programming problemsBack to roadmap