DP: Unique Paths (Grid)
Easy+80 XPCount right/down paths across a grid — the clearest 2D DP, where the table IS the map.
No visualization loaded.
Watch
—
Press Run to begin.
A robot sits in the top-left corner of a grid and wants to reach the bottom-right corner. It can only step RIGHT or DOWN — never back. How many different paths are there? The insight: to stand in any cell, the robot's last step came either from the cell directly ABOVE or the cell directly to the LEFT. So the number of paths into a cell = paths into the cell above + paths into the cell on its left. Fill the grid from the start corner and the bottom-right cell holds the total.
▸Why does each cell just add the cell above and the cell to its left?
Because those are the only two cells the robot could have stepped FROM (it moves only right or down). Every path that ends here passed through exactly one of them as its second-to-last cell, and those two sets don't overlap — so you add their counts. No path is missed, none is double-counted.
▸Why is the whole top row and left column all 1's?
Along the top row the robot can only have come from the left (there's nothing above), so there's a single straight path to each — exactly 1 way. Same for the left column from above. The edges are the simple base case the rest of the grid builds on.
▸How is this the same idea as Climbing Stairs?
Climbing Stairs is this in ONE dimension: each step = the two steps before it, added. Grid paths is the 2D cousin: each cell = the two cells before it (up and left), added. Same 'combine smaller solved answers,' just on a grid instead of a line.
▸What if there were walls (blocked cells)?
Then a blocked cell holds 0 paths (you can't stand on it), and cells beyond it simply add in that 0. The recurrence doesn't change — that's the beauty of the table. Same trick handles 'minimum-cost path' too: instead of ADDING the two sources, take the cheaper one and add the cell's own cost.
How the work grows
O(rows × cols) is slow — explodes on big inputs. You fill every cell of the grid exactly once, each in O(1) from two neighbors: rows×cols work. Brute-force enumerating every path is exponential (the count itself grows huge), so the table is essential. Memory is the grid, though you only ever need the previous row.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.