DSA Tracker

Visualize

Unique Paths II

dp[i][j] = dp[i-1][j] + dp[i][j-1], forced to 0 at an obstacle

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

Every path that reaches a cell arrived from directly above or directly from the left — there is no third way to get there, since the robot never moves up or left. So the number of paths to a cell is just the sum of the paths to those two neighbors, EXCEPT an obstacle cell has no paths through it at all, and that zero then starves every cell downstream that could only be reached that way.

Details

Animated on: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] — a robot moves only down or right from the top-left corner. Count the unique paths to the bottom-right corner, avoiding cells marked 1.

Problem:Unique Paths IIMedium

dp[i][j] = dp[i-1][j] + dp[i][j-1], forced to 0 at an obstacle

step 1 / 9

(0,0) is clear, so the robot already has exactly one way to be standing here: dp[0][0] = 1.

Pseudocode
1FUNCTION uniquePathsWithObstacles(grid):
2  m <- ROWS(grid), n <- COLS(grid)
3  FOR i FROM 0 TO m-1:
4    FOR j FROM 0 TO n-1:
5      IF grid[i][j] = 1:
6        dp[i][j] <- 0
7      ELSE IF i = 0 AND j = 0:
8        dp[i][j] <- 1
9      ELSE:
10        above <- IF i > 0 THEN dp[i-1][j] ELSE 0
11        left <- IF j > 0 THEN dp[i][j-1] ELSE 0
12        dp[i][j] <- above + left
13  RETURN dp[m-1][n-1]

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. (0,0) is clear, so the robot already has exactly one way to be standing here: dp[0][0] = 1.
  2. dp[0][1] = above (0) + left (1) = 1: every way to be standing above or to the left carries forward into this cell.
  3. dp[0][2] = above (0) + left (1) = 1: every way to be standing above or to the left carries forward into this cell.
  4. dp[1][0] = above (1) + left (0) = 1: every way to be standing above or to the left carries forward into this cell.
  5. (1,1) is an obstacle — no path can stand here, so dp[1][1] = 0 no matter what arrives from above or the left.
  6. dp[1][2] = above (1) + left (0) = 1: every way to be standing above or to the left carries forward into this cell.
  7. dp[2][0] = above (1) + left (0) = 1: every way to be standing above or to the left carries forward into this cell.
  8. dp[2][1] = above (0) + left (1) = 1: every way to be standing above or to the left carries forward into this cell.
  9. Every path must arrive from above or the left, so dp[2][2] = 1 + 1 = 2 — the total number of paths 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 II in the editorAll Dynamic Programming problemsBack to roadmap