Difficulty: Medium2-D Dynamic Programming

Unique Paths

Problem in Plain English

A robot on an m by n grid can only move down or right. Count how many different routes lead from the top-left corner to the bottom-right corner.

Problem Statement

A robot starts at the top-left cell (0, 0) of an m x n grid and must reach the bottom-right cell (m - 1, n - 1). Each move goes one cell down or one cell right, staying inside the grid.

Return the number of distinct routes. Two routes differ if their move sequences differ. There are no obstacles, and the starting cell itself requires no move. Inputs guarantee that the answer is at most 2000000000.

Constraints

1 <= m, n <= 100
Inputs guarantee that the number of routes is at most 2000000000.

Examples

Example 1

Input: m = 3, n = 2
Output: 3

Every route has two down moves D and one right move R. The three possible orders are DDR, DRD, and RDD; all remain inside the grid and end at (2, 1).

Example 2

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

There are eight moves in total: two downs and six rights. Choose the two down positions among eight positions: $8 * 7 / 2 = 28$ . Each choice determines one distinct route.

Example 3

Input: m = 2, n = 2
Output: 2

One down and one right can be ordered as DR or RD. Reaching the same destination does not make their move sequences identical.

Example 4

Input: m = 1, n = 1
Output: 1

The robot already occupies the destination. The empty move sequence is one valid route, so the answer is 1, not 0.

Example 5

Input: m = 1, n = 100
Output: 1

There is no room for a down move. The only route consists of 99 right moves; maximum width alone does not imply many routes.

Intuition

Count routes by the choices that distinguish them. In a 3 x 2 grid, every route makes two down moves and one right move: DDR, DRD, or RDD. Recursive search counts these choices one branch at a time, but different prefixes repeatedly reach the same cell. Because every route contains exactly the same numbers of the two move types and there are no obstacles, choosing the positions of the right moves counts the routes directly. This replaces repeated grid exploration with one binomial coefficient, the number of ways to choose positions from a fixed set.

Approaches

Brute Force Recursion

Solution Details

Reveal Brute Force Recursion: intuition, complexity, and code

Intuition

Count the routes from a cell by trying each legal next move and adding the resulting suffix counts. The destination contributes one completed route. In Example 1, the down-first branch contains DDR and DRD, and the right-first branch contains RDD. This exposes the counting recurrence but recomputes a suffix whenever several prefixes reach the same cell.

Step-by-Step Logic

Define dfs(r, c) as the number of remaining routes. Return 1 when both coordinates equal the destination, including when the grid is 1 x 1.
At any other cell, start ways = 0. If a down move stays inside the grid, add dfs(r + 1, c); then do the same for a legal right move. No out-of-grid calls are created.
For Example 1, enter (0, 0) and explore down first. From (1, 0), the down child (2, 0) has only the right child (2, 1), contributing one route DDR.
The right child of (1, 0) is (1, 1), whose down child reaches the goal. Its count is one for DRD, making dfs(1, 0) = 1 + 1 = 2.
Return to (0, 0) with ways = 2. Its right child (0, 1) goes down through (1, 1) to the goal, contributing one for RDD. This recomputes (1, 1) rather than caching it.
Return the root sum 2 + 1 = 3. Local ways values count suffixes of their own calls; there is no shared global counter.

Why It Works

Let dfs(r, c) count routes from (r, c) to the destination. At the destination there is exactly one route, the empty suffix. At every other cell, a legal route starts either down or right. These groups are disjoint because their first moves differ, and they include all legal routes because no other moves are allowed. Inducting on the remaining distance, each child returns its exact suffix count, and their sum is the exact parent count. Skipping an out-of-grid neighbour contributes no route. Every call moves closer to the goal, so recursion terminates; the root counts all routes from the start.

Dry Run

Brute Force Recursion: variable states at each step
Event	Current call	Local `ways` change / return	Meaning
enter	`(0, 0)`	initialize `0`; call down `(1, 0)`	root waits for child
enter	`(1, 0)`	initialize `0`; call down `(2, 0)`	down-first branch
enter	`(2, 0)`	initialize `0`; down forbidden, call right `(2, 1)`	bottom row
goal	`(2, 1)`	return `1` without initializing `ways`	completed `DDR`
resume and return	`(2, 0)`	right contributes `1`: `0 -> 1`; return `1`	no further move
resume	`(1, 0)`	down contributes `1`: `0 -> 1`; call right `(1, 1)`	one child remains
enter	`(1, 1)`	initialize `0`; call down `(2, 1)`	right edge
goal	`(2, 1)`	return `1`	completed `DRD`
resume and return	`(1, 1)`	down contributes `1`: `0 -> 1`; right forbidden; return `1`	first evaluation of this suffix
resume and return	`(1, 0)`	right contributes `1`: `1 -> 2`; return `2`	both down-first routes counted
resume	`(0, 0)`	down contributes `2`: `0 -> 2`; call right `(0, 1)`	root down branch complete
enter	`(0, 1)`	initialize `0`; call down `(1, 1)`	right-first branch
enter again	`(1, 1)`	initialize a new `0`; call down `(2, 1)`	repeated suffix, no memoization
goal	`(2, 1)`	return `1`	completed `RDD`
resume and return	`(1, 1)`	down contributes `1`: `0 -> 1`; right forbidden; return `1`	repeated suffix result
resume and return	`(0, 1)`	down contributes `1`: `0 -> 1`; right forbidden; return `1`	right-first count
resume and return	`(0, 0)`	right contributes `1`: `2 -> 3`; return `3`	Example 1 answer

Complexity Analysis

Time Complexity

O(2^{m+n})

Space Complexity

O(m+n)

Each call has at most two children and a root-to-goal route has m + n - 2 moves, giving the stated loose exponential upper bound on the recursion tree. Narrow grids branch less; a single row or column takes O(m + n) time. One active call chain contains at most m + n - 1 frames, each holding only coordinates and a count. No grid, route list or memo table is allocated. Counts fit Java int: for any reached cell, prepend one fixed start-to-cell prefix to every suffix route to inject those routes into the full route set, so its count cannot exceed the promised final bound. Raw recursion remains impractical for highly branching valid inputs.

Code

Solution.java

1class Solution {2    public int uniquePaths(int m, int n) {3        return dfs(0, 0, m, n);4    }5
6    private int dfs(int r, int c, int m, int n) {7        // The empty suffix at the destination is one completed route.8        if (r == m - 1 && c == n - 1) {9            return 1;10        }11        int ways = 0;12        // Only legal children contribute; their first moves distinguish the routes.13        if (r + 1 < m) {14            ways += dfs(r + 1, c, m, n);15        }16        if (c + 1 < n) {17            ways += dfs(r, c + 1, m, n);18        }19        return ways;20    }21}

Hints

Hint 1

From a cell, separate routes by whether their first move is down or right. What count should the destination contribute?

Hint 2

Every complete route makes the same numbers of downs and rights. For 3 x 2, write every ordering of two D moves and one R move.

Hint 3

Choosing the positions of the downs determines the rights too. Use

C(m+n-2, m-1)

or its symmetric choice for right positions.

Hint 4

Compute the coefficient incrementally with res = res * (total - r + i) / i. Explain why this entire quotient is integral and why the temporary product needs a wider type than the return value.

Edge Cases

A 1 x 1 grid has one empty route. Both approaches must return 1 without requiring a move.
A single row or column has one straight route. Recursion follows one chain, and the combinatorial loop has zero iterations.
Swapping m and n does not change the answer: exchanging down and right creates a one-to-one correspondence between routes.
For m = 18, n = 17, the answer is 1166803110. The last product is 18668849760 before division by 16, so Java needs long even though the result fits int.
The dimension limits and the answer promise both apply: 100 x 100 is outside the guaranteed input set because its route count exceeds 2000000000. Do not use it as a valid overflow test.
There are no blocked cells. Adding obstacles breaks the move-position bijection because some arrangements would hit a blocked cell; use cell-based DP for that variant.

Common Mistakes and Interview Tips

Using m + n moves or choosing m downs counts steps from dimensions instead of subtracting the already occupied starting row and column.
Returning 0 at the destination loses every completed route. The destination contributes one empty suffix.
Merging recursive calls just because they reach the same cell without preserving their counts loses distinct prefixes. Memoization may reuse a suffix count, but each incoming branch still adds it.
Building factorials for the binomial formula can overflow even when the final ratio is small. Divide at every multiplicative step instead.
Dividing (total - r + i) by i before multiplying can truncate: for 3 x 3, the second factor is 4 / 2, but other steps such as 3 x 4 include 5 / 2. The full product is divisible, not necessarily an individual factor.
Keeping the Java temporary product in int overflows on valid grids such as 18 x 17. Starting res as long makes multiplication wide before division.
Interview tip: justify both directions of the route-to-position correspondence, then state the answer promise before claiming that JavaScript arithmetic or the final Java cast is safe. Raw recursion is a teaching baseline, not a practical solution for highly branching large inputs.

Key Takeaway

When every solution orders a fixed multiset of choices and every ordering is legal, count position selections with a binomial coefficient instead of enumerating paths. Check the bijection and intermediate arithmetic bounds first; obstacles or extra movement rules can invalidate the shortcut.