Unique Paths

Think about the robot's last move into the bottom-right cell. It came either down from the cell above or right from the cell to the left, never both. So the paths through an m × n grid are the paths through the grid one row shorter, uniquePaths(m-1, n), plus the paths through the grid one column narrower, uniquePaths(m, n-1).

The recursion stops at a grid with one row or one column, where the robot can only go straight, so there is exactly 1 path. Every path ends with one of the two moves, so each path is counted once and the total is right.

It is slow because every path ends in a base case that returns 1, so the number of calls is at least the answer itself. A 17 × 17 grid takes more than 600 million calls, and the tests go up to answers near 1.6 × 10^9. The same smaller grids are worked out many times: (m-1, n-1) is reached once from each of its two parents, and the repeats multiply as you go down.

The recursion asks about the same cells again and again, and there are only m × n cells. Count the paths into each cell once, in an order where the cells you need are always ready.

State: paths[r][c] is the number of paths from the top-left cell to row r, column c. Recurrence: paths[r][c] = paths[r-1][c] + paths[r][c-1], the paths that arrive from above plus the paths that arrive from the left. Base cases: every cell in the top row and in the left column has 1 path, a straight line. Order: row by row, left to right, so the cell above and the cell to the left are filled before you need them.

For m = 3 and n = 4 the rows are 1 1 1 1, then 1 2 3 4, then 1 3 6 10, and the answer is the last cell, 10.

Now look at what the fill reads: only the row above and the row you are filling. So keep one row. Before you update row[c] it still holds the count from the row above, and row[c-1] already holds the new count to its left, so row[c] += row[c-1] is the whole recurrence. The time stays O(m × n), and the memory drops from O(m × n) to O(n).

Every path makes exactly m-1 moves down and n-1 moves right, m+n-2 moves in all, in some order. Every order is a valid path: the robot never makes more than m-1 downs or n-1 rights, so it never leaves the grid. A path is therefore the same thing as a choice of which m-1 of the m+n-2 moves go down, and the answer is the binomial coefficient C(m+n-2, m-1).

The table from the last approach is Pascal's triangle turned on its side, which is why the two agree. To compute the coefficient without huge factorials, build it one factor at a time. With N = m+n-2 and k = min(m, n)-1, multiply by N-k+i and then divide by i, for i from 1 to k. After step i the running value is C(N-k+i, i), a whole number, so every division is exact.

For m = 3 and n = 4: N = 5, k = 2, and the value goes 1 × 4 / 1 = 4, then 4 × 5 / 2 = 10. Choosing along the shorter side keeps the loop at 99 steps or fewer. The product before the last division is k times the answer. For a 17 × 17 grid that is 16 × 601,080,390, about 9.6 × 10^9, past the 32-bit range, so keep it in a 64-bit integer.