Problem 29.1 · DP on GridsMedium

Unique Paths

What it teaches: The basic grid DP, then the one-row version.

Practise it on judges as “Unique Paths”.

The problem

A robot at the top-left of an m × n grid moves only right or down. How many paths reach the bottom-right?

Example 1

Input: m = 3, n = 7
Output: 28

Constraints

1 ≤ m, n ≤ 100
Answer ≤ 2 × 10⁹

Pattern clues in the wording

→ Count paths with right/down moves

These clues point to Grid DP: Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int uniquePaths(int m, int n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	m = 3 n = 7	28
2	m = 3 n = 2	3
3	m = 1 n = 1	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. One-row DP · O(m × n)2. Combinatorics · O(min(m, n))

One-row DP

Time O(m × n) Space O(n)

dp[c] = 1 initially; for each later row, dp[c] += dp[c − 1] left to right.

Approach 1

import java.util.Arrays;

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int r = 1; r < m; r++)
            for (int c = 1; c < n; c++) dp[c] += dp[c - 1];
        return dp[n - 1];
    }
}

Verdict: Standard.

Combinatorics

Time O(min(m, n)) Space O(1)

A path is a sequence of m − 1 downs and n − 1 rights: C(m + n − 2, m − 1). Compute it incrementally with long.

Approach 2

class Solution {
    public int uniquePaths(int m, int n) {
        long result = 1;
        int k = Math.min(m, n) - 1, total = m + n - 2;
        for (int i = 1; i <= k; i++) result = result * (total - k + i) / i;
        return (int) result;
    }
}

Verdict: Fast, but only for the obstacle-free version.

Before you submit

Edge cases and common mistakes

Test these inputs

1 × n or m × 1 (one path)

Mistakes people make

Factorials overflowing (compute the binomial incrementally).

Interview

Follow-up questions

Why is result × (total − k + i) / i always exact?

Command Palette