• 1 ≤ m, n ≤ 100
• Movement is restricted to right and down only
• The grid is empty — every cell is walkable
• The answer fits in a signed 32-bit integer

The robot only moves right or down, so it can never revisit a cell and never go backwards. Every path is just a sequence of moves, and we want to count them.

Notice what the movement rule buys us. Because the robot only moves right or down, a cell can only be reached from the cell above it or the cell to its left. Two ways in — and we build everything on exactly that.

Stand on any cell (r, c) and ask how the robot got there. Its last move was either a step down (so it was at (r-1, c)) or a step right (so it was at (r, c-1)). No third option, and the two cases never overlap, because a path's last move is a single definite thing.

So the number of paths ending at (r, c) is the number ending at the cell above plus the number ending at the cell to the left.

f(r, c) = f(r-1, c) + f(r, c-1)

Base cases come from the edges. Any cell in the top row can only be reached by walking straight right from the start — there is no row above to come from — so there is exactly 1 path to each of them. Likewise any cell in the leftmost column has exactly 1 path. And f(0, 0) = 1, the empty path: the robot is already there.

Because we are counting, we add the two branches. (A min or max would be for a best-value question; here we just want how many.)

Plain recursion first:

def unique_paths(m, n):
    def f(r, c):
        if r == 0 or c == 0: return 1        # top row or left column: one way
        return f(r - 1, c) + f(r, c - 1)
    return f(m - 1, n - 1)

Two branches per call and a depth of about m + n, so this is exponential — while there are only m × n genuinely different cells. Almost every cell in the middle is recomputed from many different directions. Memoise it:

def unique_paths(m, n):
    memo = {}
    def f(r, c):
        if r == 0 or c == 0: return 1
        if (r, c) in memo: return memo[(r, c)]
        memo[(r, c)] = f(r - 1, c) + f(r, c - 1)
        return memo[(r, c)]
    return f(m - 1, n - 1)

m × n states, constant work each: O(M × N).

Now build a table instead of recursing. Let dp[r][c] hold what f(r, c) returned — the number of paths to cell (r, c). Swap the calls for array reads and the recurrence becomes:

dp[r][c] = dp[r-1][c] + dp[r][c-1]

dp[r][c] needs the cell above and the cell to the left, both at smaller indices. So fill the grid top-to-bottom, left-to-right, and both are ready when you reach (r, c). The base cases copy straight from the recursion: it returned 1 whenever r == 0 or c == 0, so the whole top row and left column start at 1. The loops then begin at (1, 1), and the answer is dp[m-1][n-1]:

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]     # top row and left column start at 1
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[m - 1][n - 1]

Initialising the whole grid to 1 quietly handles both base cases at once, since the loops never touch row 0 or column 0.

When you compute row r left to right, the value you need from above is dp[r-1][c], and the value you need from the left is dp[r][c-1] — which you just computed on this same row. So a single array works, if you read it at the right moment:

def unique_paths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] = row[c] + row[c - 1]
            #        ^above    ^left (already updated this row)
    return row[n - 1]

The trick is that row[c] still holds the previous row's value at the instant you read it, and row[c-1] already holds this row's — so one array plays both parts. This overlapping-read pattern shows up in every grid problem where a cell depends on up and left, so it is worth staring at until it feels obvious.

1  1  1
1  ?  ?
1  ?  ?

1  1  1
1  2  3
1  3  6

Answer 6. Check it by hand: the robot makes 2 downs and 2 rights in some order, and the distinct orderings of DDRR are DDRR, DRDR, DRRD, RDDR, RDRD, RRDD — six.

That hand-check hints at something. Every path from corner to corner makes exactly m-1 downward moves and n-1 rightward moves, in some order — always the same counts, no matter the route. So a path is completely described by which of the m+n-2 moves are the downward ones. The number of ways to choose that is the binomial coefficient:

C(m + n - 2, m - 1)

For a 3 × 7 grid that is C(8, 2) = 28, matching the table. This closes the problem in O(min(m, n)) time with no table at all, and it is worth mentioning in an interview — it shows you saw the structure rather than just applying machinery.

But be honest about its limits. The formula works only because the grid is empty and every route is legal. Put a single obstacle in the way and the counting argument collapses, because paths are no longer interchangeable. The table survives that change with a one-line edit. The general lesson: a closed-form shortcut is usually more fragile than the table that produced it, so know both and know which assumption each one leans on.