Unique Paths: Grid DP and Math

Unique Paths is the friendliest grid DP problem and one of the few interview questions with a clean closed-form answer. The DP is a one-paragraph derivation; the math is a one-line answer. Knowing both signals breadth, but only one of them is the right thing to write down first.

The Problem

A robot sits in the top-left cell of an m x n grid. It can move only right or down. Return the number of distinct paths from the top-left cell to the bottom-right cell.

Intuition

Every cell other than the start can be reached either from the cell above or from the cell to its left, so dp[r][c] = dp[r - 1][c] + dp[r][c - 1]. The first row and first column are filled with 1s because there is exactly one path along an edge. Since each row only depends on the row above and the cell to the left, a single 1D row that we update in place is enough.

The math view: every path consists of m - 1 down moves and n - 1 right moves in some order, so the count is C(m + n - 2, m - 1). Same answer, no table.

Explanation with Example

For a 3 x 7 grid:

The DP fills row by row:

1 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 6 10 15 21 28

Answer: 28. The closed form agrees: C(8, 2) = 28.

The 1D rolling version computes the third row directly by repeatedly adding the running prefix sum to each cell — same numbers, half the memory.

        j=0  j=1  j=2  j=3  j=4  j=5  j=6  j=7
i=0:     1    1    1    1    1    1    1    1
i=1:     1    2    3    4    5    6    7    8
i=2:     1    3    6   10   15   21   28   28*

* = answer dp[m-1][n-1] = 28 = C(8,2)

Code

Three flavors: the 2D DP for clarity, the 1D rolling-row optimization, and the closed-form binomial coefficient.

from math import comb

# 1D rolling row
def uniquePaths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[n - 1]


# Closed form
def uniquePaths_math(m, n):
    return comb(m + n - 2, m - 1)

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

#include <vector>
using namespace std;

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> row(n, 1);
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                row[c] += row[c - 1];
            }
        }
        return row[n - 1];
    }
};

Edge Cases

• A 1 x n or m x 1 grid — only one path. The base-row initialization handles this. The closed form gives C(n - 1, 0) = 1.
• m = n = 1 — the robot is already at the goal. Answer is 1.
• Very large grids — the DP uses big arrays; the closed form is a single integer computation. Python handles big ints natively. In C++ you would need a careful multiplicative loop to avoid overflow.

Complexity Analysis

The 2D DP is O(m * n) time and O(m * n) space. The 1D rolling version is O(m * n) time and O(n) space. The closed form is O(min(m, n)) time using a multiplicative binomial — or even O(1) if you accept Python’s arbitrary precision arithmetic as a single step.

The brute force without memoization is exponential because it counts paths by enumerating them.

How to Explain It in an Interview

Open with the recurrence in plain English: “Every cell other than the start can be reached from above or from the left, so its path count is the sum of those two.” Write the 2D DP. Volunteer the rolling optimization without being asked — it costs one line of code and demonstrates space awareness.

Only then mention the closed form: “We are choosing which m - 1 of m + n - 2 steps go down, so the answer is C(m + n - 2, m - 1).” Calling this out establishes that you know the math but did not skip past the DP that the interviewer wanted to see. Avoid the temptation to write only the closed form; many interviewers will count that as ducking the question.

Related Problems

• Unique Paths II (obstacles; closed form no longer applies)
• Minimum Path Sum
• Unique Paths III (backtracking, every cell must be visited)
• Dungeon Game

Notice how adding even one obstacle removes the closed form — that is a useful reminder that combinatorial shortcuts are fragile.

Wrap up

Unique Paths is the grid-DP starter pack. Lock in three artifacts: the 2D table, the 1D rolling row, and the binomial formula. Pair this problem with Classic DP Problems and you will be fluent in the prefix-sum-on-a-grid style that powers half of dynamic programming interviews. Then, when the variant with obstacles shows up, you already know exactly which line in the recurrence to guard.