Unique Paths

Problem statement

A robot starts at the top-left of an m × n grid and wants the bottom-right. It may move only right or down. Return how many distinct paths exist.

Example:

Input:

m = 3, n = 2

Expected output:

3

The three paths (D = down, R = right): DDR, DRD, RDD.

A larger one: m = 3, n = 7 has 28 paths.

Practice on LeetCode: Unique Paths

What we are counting

Label the 3 × 2 grid:

A B
C D
E F

A is the start. F is the end. From A you can go to C or B. From B you can only go down. From E you can only go right.

The number of paths from a cell to F is the number from the cell below, plus the number from the cell to the right. F itself is 1 — you are already there, one empty path.

from(i, j) = from(i+1, j) + from(i, j+1)
from(m-1, n-1) = 1

Fill that in from the end:

3 1
2 1
1 1

A is 3. That is the answer.

Why not recurse without a table

Every cell branches two ways. The same cell is asked over and over — D is on every path that went through B and every path that went through C. Without memory the tree is exponential.

There are only m · n cells. Remember the answer for each cell the first time you finish it. Then every later visit is O(1).

That is the overlapping-subproblem version of DP. Bottom-up fills the same recurrence from F back to A and needs no call stack.

Golang Solution

dp[i][j] is paths from (i, j) to the end. unique returns a cached value when it is already positive. Otherwise it walks down and right (when those cells exist), stores the sum, and returns it. The start cell is dp[0][0].

Time: O(m · n) — each cell is solved once
Space: O(m · n) — table, plus O(m + n) recursion depth

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    dp[0][0] = unique(m, n, 0, 0, dp)
    return dp[0][0]
}

func unique(m, n, i, j int, dp [][]int) int {
    if dp[i][j] > 0 {
        return dp[i][j]
    }

    if i == m-1 && j == n-1 {
        return 1
    }

    down, right := 0, 0
    if i < m-1 {
        down = unique(m, n, i+1, j, dp)
    }
    if j < n-1 {
        right = unique(m, n, i, j+1, dp)
    }
    dp[i][j] = down + right
    return dp[i][j]
}

m = 1, n = 1 hits the base case on the first call and returns 1. The memo test dp[i][j] > 0 is safe because every finished cell has at least one path.

You also need exactly m-1 downs and n-1 rights, in some order. That count is the binomial coefficient C(m+n-2, m-1). The DP is the version that still works when the grid later grows obstacles.