Unique Grid Paths
paths(r, c) = paths(r-1, c) + paths(r, c-1); Pascal's triangle on a grid.
Decision · step 7 of 14DP on a Grid: Paths on a 3 x 4 grid
(1, 1) can be entered from above, 1 way, or from the left, 1 way. Those are disjoint, so 1 + 1 = 2.
What you will see
Each cell sums the cell above and the cell to the left; values grow toward the corner.
Cost
| Best | O(r * c) |
|---|---|
| Average | O(r * c) |
| Worst | O(r * c) |
| Space | O(c) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
Taught by the same lesson
DP on a Grid covers these too, in the same run.