Pattern visualizer
Grid Unique Paths with Obstacles
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. 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..
dp[i][j] = dp[i-1][j] + dp[i][j-1], forced to 0 at an obstacle
(0,0) is clear, so the robot already has exactly one way to be standing here: dp[0][0] = 1.
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] <- 07 ELSE IF i = 0 AND j = 0:8 dp[i][j] <- 19 ELSE:10 above <- IF i > 0 THEN dp[i-1][j] ELSE 011 left <- IF j > 0 THEN dp[i][j-1] ELSE 012 dp[i][j] <- above + left13 RETURN dp[m-1][n-1]
← / → step · space play · Home restart