In a right-and-down-only grid, why is a cell's route count the sum of the cells above and left?
answer
- think about the very last step
- how can a route enter this cell
- only two predecessors exist here
- can one route arrive from both?
- disjoint alternatives mean counts add
basics
~20 sEvery route into a cell takes its last step from either the cell above or the cell to its left. Those two sets of routes are disjoint and together cover every route, so the two counts simply add.
solid answer
~40 sFix a cell and look only at the final step of any route that ends there. Because moves are restricted to right and down, that step came from exactly one of two cells: the one directly above or the one directly to the left. No route arrives from both, so the sets do not overlap and nothing needs subtracting; no other cell can be the predecessor, so nothing is missed. That makes `routes[i][j] = routes[i-1][j] + routes[i][j-1]`, with the top row and left column seeded to 1 on an open grid because there is a single straight-line approach along each border. Filling the table left to right, row by row, is `O(m*n)` time and `O(m*n)` space, and every cell is evaluated exactly once.
go deeper
Be ready to state the recurrence and its border seeds out loud, and to fill a three-by-four grid by hand in under a minute without hesitating on the base row.
Expect to justify why the two predecessor sets are disjoint and exhaustive, and to give the time and space bounds plus the cost of the un-memoized recursion without hedging.
Show that you know when the table is the wrong tool — an open floor has a closed-form count, and per-cell costs turn counting into optimizing with the same skeleton. Name the memory footprint at real grid sizes.
Own the framing before the recurrence: does the product need a count, a single cheapest route, or every route enumerated? The first two are cheap table fills; the third has exponential output and no technique rescues it.
## The setting Picture a warehouse floor as a rectangular grid of `m` rows and `n` columns. A picking robot starts in the top-left cell, must finish in the bottom-right cell, and physically can only drive one aisle to the right or one aisle down — it never reverses. The question "how many distinct routes exist?" is the smallest complete example of grid dynamic programming, and it is worth being able to derive rather than recite. ## The state Define `routes[i][j]` as the number of distinct routes from the start cell to cell `(i, j)`. That single number is the entire state: it does not matter which of those routes was taken, how long ago, or in what order the moves happened. Everything the rest of the computation needs about cell `(i, j)` is captured by that count. This is what makes the problem a dynamic-programming problem rather than a search — the past collapses into one number per cell. ## The last-step argument Take any route that ends at `(i, j)` and delete its final move. The move was either a downward step, in which case the route previously stood at `(i-1, j)`, or a rightward step, in which case it stood at `(i, j-1)`. Two properties make the recurrence fall out: - **Exhaustive.** Those are the only two legal ways to enter the cell, so no route is unaccounted for. - **Disjoint.** A single route has exactly one last step, so it is counted under exactly one predecessor. There is no overlap to subtract. When alternatives are disjoint and exhaustive, their counts add. Multiplication would be the answer to a different question — the number of ways to make two independent choices *in sequence*, not the number of ways to make one choice *out of two*. Confusing the two is the single most common error here. ``` routes[i][j] = routes[i-1][j] + routes[i][j-1] ``` ## Base cases On an open grid, every cell in the top row has exactly one approach — drive straight right from the start — so it holds 1. The same holds down the left column. The start cell itself holds 1 (the empty route). Those seeds are not arbitrary: they are what the recurrence degenerates to when one predecessor is off the grid and therefore contributes 0. ## A worked fill A 3-row, 4-column floor fills like this: | | col 0 | col 1 | col 2 | col 3 | |---|---|---|---|---| | **row 0** | 1 | 1 | 1 | 1 | | **row 1** | 1 | 2 | 3 | 4 | | **row 2** | 1 | 3 | 6 | 10 | Ten routes. Notice the fill order: each cell is computed only after both predecessors already hold final values, which is why a simple left-to-right, top-to-bottom sweep is a valid evaluation order. ## Cost, and why the naive recursion is not this The table has `m*n` cells and each costs constant work, so the fill is `O(m*n)` time and `O(m*n)` space. The plain recursion that asks "routes to me = routes to my two predecessors" without storing anything has a completely different cost: it re-explores a subtree once per route reaching a cell, so its running time is proportional to the answer itself — which grows exponentially in grid size. Adding a memo table, or sweeping bottom-up, collapses that to one evaluation per cell. The asymptotic gap between the two is the whole reason the technique has a name. ## Why there is no visited set Engineers arriving from graph traversal often reach for a visited set out of habit, expecting to guard against revisiting a cell. Here it is unnecessary, and saying otherwise signals a misunderstanding of what the table is. Every legal move increases `i + j` by exactly one, so that quantity strictly increases along any route: a cell can never be re-entered, and cycles are impossible by construction. The subproblem graph is acyclic, and the table is a cache of answers, not a record of where a walker has been. A visited set exists to break cycles; a memo table exists to avoid recomputation. They solve different problems and one is not a substitute for the other. ## Where the shape stops being this easy Two edits break the simple version. Blocked cells invalidate the uniform border seeding, because a block in the top row makes every cell past it unreachable. Per-cell costs change the question from counting to optimizing, which swaps the `+` for a `min` over the two predecessors and keeps everything else identical. Both variants reuse the same last-step argument — only the operator and the seeds change.
- Why does this DP need no visited set, when a grid traversal usually does?Because every legal move increases row plus column by one, so that quantity strictly increases along any route and no cell can ever be re-entered. The subproblem graph is acyclic by construction. A visited set exists to break cycles; the table here exists only to avoid recomputing an answer, and those are different jobs.
- On a grid with nothing blocked, can you skip the table entirely?Yes. Any route is a fixed sequence of `m-1` downward steps and `n-1` rightward steps, so counting routes is counting which positions in that sequence are the downward ones: `C(m+n-2, m-1)`. That is `O(m+n)` arithmetic instead of `O(m*n)`. It collapses the moment blocked cells or per-cell costs appear, and the value itself explodes — a 35-by-35 floor already exceeds a signed 64-bit range.
- How would the recurrence change if the robot could also move diagonally down-right?A third disjoint predecessor joins the sum: `routes[i-1][j-1]`. The last-step argument is unchanged — the alternatives are still mutually exclusive and still exhaustive — so the counts still add. Time stays `O(m*n)` with a slightly larger constant, and the border seeding still holds because the diagonal predecessor is off-grid there.
Every guest in a room walked through one of two doors. Count the arrivals at each door and add — nobody squeezed through both at once, so there is no double-counting to correct.
saying these in an interview costs you the question
- Multiplies the two predecessor counts instead of adding them
- Subtracts an overlap that cannot exist
- Claims a visited set is needed to avoid revisiting cells
- Seeds the top row and left column with 0
- Says plain recursion is fine because the grid is small