DP on Grids

A robot starts at the top-left cell and moves only right or down. The state is simply the cell you are on.

Count the paths

Look at the last move into cell (r, c). It came from above (r − 1, c) or from the left (r, c − 1).

• Promise: f(r, c) = number of paths from (0, 0) to (r, c).
• Base cases: outside the grid → 0. The start (0, 0) → 1.
• Recurrence: f(r, c) = f(r − 1, c) + f(r, c − 1).
• Memo: int[R][C]. Time O(R · C).