Unique Paths

Problem in plain words

A robot sits in the top-left cell of an m by n grid and wants to reach the bottom-right cell. It can only move one cell right or one cell down at a time. Count how many different routes it can take.

On a 2 by 3 grid there are 3 routes: right-right-down, right-down-right and down-right-right.

Intuition

The robot can only enter a cell from above or from the left. So the number of ways to reach a cell is the number of ways to reach the cell above it plus the number of ways to reach the cell to its left. Cells in the top row and left column have exactly one route each (keep going straight). Filling the grid row by row gives every count from its neighbours, which is the same tabulation idea as the bottom-up Fibonacci DP lesson, stretched into two dimensions.

Approach

1. State: ways[r][c] is the number of routes from the start to cell (r, c).
2. Recurrence: ways[r][c] = ways[r - 1][c] + ways[r][c - 1].
3. Base cases: every cell in row 0 and column 0 has value 1.
4. Order: row by row, left to right. Since a row only needs the row above, keep one array row of length n: before the update row[c] still holds the value from above, and row[c - 1] already holds the new left value, so row[c] += row[c - 1].
5. Return row[n - 1].

Dry run

Input: m = 3, n = 4. The single row evolves like this:

The answer is 10.

Java solution

class Solution {
    public int uniquePaths(int m, int n) {
        int[] row = new int[n];
        Arrays.fill(row, 1);               // top row: one way to each cell
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                row[c] += row[c - 1];      // from above + from the left
            }
        }
        return row[n - 1];
    }
}

Python solution

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n                  # top row: one way to each cell
        for _ in range(1, m):
            for c in range(1, n):
                row[c] += row[c - 1]   # from above + from the left
        return row[-1]

Complexity

Edge cases and common mistakes

• A single row or column: with m = 1 or n = 1 there is exactly one route; the loops do not run and the answer stays 1.
• Initialising the edges to 0: the first row and column must be 1, otherwise every count stays 0.
• Starting the inner loop at 0: row[0] must remain 1; updating it would read row[-1].
• Recursion without a cache: plain recursion explores every path and is exponential. Add memoization or use the table.