Counting grid paths, top-down then bottom-up

Question

A robot starts at the top-left of an m 	imes n grid and moves only right or down until it reaches the bottom-right. The number of distinct paths satisfies with paths(0, j) = paths(i, 0) = 1 along the top row and left column. Explain why plain recursion is exponential and rewrite it to run in O(mn).

Accepted Answer

The naive recursion revisits interior cells over and over: the cell (i-1, j-1) is reached both from (i-1, j) and from (i, j-1), and that overlap compounds across the grid, giving exponentially many calls. But there are only mn distinct cells. Fill a table once, each cell reading its neighbor above and to the left: For a 3 	imes 3 grid the table fills to a bottom-right value of 6, matching the closed form \binom{m+n-2}{m-1} = \binom{4}{2} = 6. Time O(mn), space O(mn) (shrinkable to O(n) by keeping only the current row). Takeaway. This is Fibonacci's overlapping-subproblems idea in two dimensi…

Counting grid paths, top-down then bottom-up

Your answer

More Coding questions