AlgoScope

Unique Grid Paths

paths(r, c) = paths(r-1, c) + paths(r, c-1). Pascal's triangle on a grid.

Dynamic programming, algorithm, beginner
There are 10 paths. The table was filled once, cell by cell.01230121111123413610
There are 10 paths. The table was filled once, cell by cell.01230121111123413610

DP on a Grid: Paths on a 3 x 4 grid

Result, step 14 of 14

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)

Leads to

Topics that need this one first.

Taught by the same lesson

DP on a Grid covers these too, in the same run.