We have a grid with m rows and n columns. A robot starts at the top-left cell and needs to reach the bottom-right cell. At every step, it can only move right or down. We need to count how many distinct sequences of moves lead from the start to the destination.

One structural fact drives every approach below: the robot always makes exactly (m - 1) down moves and (n - 1) right moves. The total move count is fixed at (m - 1) + (n - 1) = m + n - 2. The only thing that varies between paths is the order of those moves. Counting unique paths is therefore the same as counting the ways to arrange a fixed set of "down" and "right" moves.

That framing connects the problem to combinatorics. We can also solve it with dynamic programming by building up the count cell by cell, which is where we'll start.

Key Constraints:

Intuition

The count of paths from a cell breaks down into the counts from its two neighbors. From any cell (i, j), the robot can move right to (i, j + 1) or down to (i + 1, j). The number of unique paths from (i, j) to the bottom-right corner is the sum of the two:

paths(i, j) = paths(i + 1, j) + paths(i, j + 1)

The base case is the destination cell (m - 1, n - 1), which has exactly one path (staying put). A cell that falls outside the grid contributes 0.

This is correct but slow. The recursion branches into two calls at every cell, and the same cell is recomputed many times along different paths, giving exponential running time.

Algorithm

Example Walkthrough

Code

The exponential cost comes entirely from recomputing the same cells. Storing each cell's result once removes that waste, which leads to a bottom-up dynamic programming table.

Intuition

Instead of recursing top-down, we build the answer bottom-up. The table dp holds, at dp[i][j], the number of unique paths from the top-left corner to cell (i, j). The previous approach counted paths from a cell to the destination; here we count paths into a cell from the start. Both directions give the same total at the corner.

Since the robot can only arrive at (i, j) from above or from the left, the recurrence is:

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

The first row and first column are all 1s: there is one way to reach any cell in the first row (move right the whole way) and one way to reach any cell in the first column (move down the whole way).

Algorithm

Example Walkthrough

Code

The time is optimal, but each row depends only on the row directly above it, so storing the full grid is wasteful. The next approach keeps a single row and overwrites it in place.

Intuition

Since each row of the DP table depends only on the row directly above it, we can collapse the 2D table into a single 1D array of length n. We process one row at a time and overwrite the array in place. The update dp[j] = dp[j] + dp[j - 1] reuses the same array slot to mean "above" before the write and "current row" after it, which reproduces the 2D recurrence with O(n) space.

Algorithm

Example Walkthrough

Code

The DP approaches still fill in every cell. Because the answer is a single binomial coefficient, the final approach computes it directly in O(min(m, n)) time without any table.

Intuition

The robot needs to make exactly (m - 1) down moves and (n - 1) right moves, for a total of (m + n - 2) moves. Every unique path corresponds to a unique ordering of these moves. So we need to choose which (m - 1) of the (m + n - 2) positions will be "down" moves. The answer is:

C(m + n - 2, m - 1) = (m + n - 2)! / ((m - 1)! * (n - 1)!)

Computing the factorials directly would overflow long before the final division shrinks the value back down. Instead we build the result one term at a time, multiplying then dividing on each step. After the i-th step the accumulator equals C(total - choose + i, i), which is always a whole number, so the integer division never drops a remainder. We also reduce the work by choosing min(m - 1, n - 1) for the loop count, since C(N, k) = C(N, N - k).

Algorithm

Example Walkthrough

Code