Unique Grid Paths
paths(r, c) = paths(r-1, c) + paths(r, c-1). Pascal's triangle on a grid.
DP on a Grid: Paths on a 3 x 4 grid
10 paths. Each of the 12 cells was computed once from two known neighbours: O(rows x cols) instead of trying every route. This is Pascal's triangle tilted: the answer is C(5, 2).
Cost
- Best
- O(r * c)
- Average
- O(r * c)
- Worst
- O(r * c)
- Space
- O(c)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
DP on a Grid covers these too, in the same run.