Unique Paths

How to Think Through a Grid DP Problem From Scratch

Unique Paths tests whether you can recognize a counting dynamic programming pattern and model state correctly. It's a classic interview question because the logic scales cleanly to harder grid problems. Once you've internalized the thinking here, a whole family of harder problems opens up.

Problem Statement

A robot is located at the top-left corner of an m × n grid.

The robot can only move either down or right at any point in time.

The robot is trying to reach the bottom-right corner of the grid.

Return the number of unique paths the robot can take to reach the destination.

1. Clarify Requirements Before Jumping Into Code

Before writing anything, let's make sure the rules are clear.

Input: Two integers m (rows) and n (columns)

Output: Number of unique paths from (0, 0) to (m-1, n-1)

Allowed moves: Right, Down

Quick edge checks:

• What if m = 1 or n = 1? There's only one path, so you can only move in one direction.

• No obstacles in this version.

• The robot must stay inside the grid.

Getting these clarifications out loud in an interview signals that you think carefully before you code.

2. Identify the Category of the Problem

This is a counting problem on a grid. When you see those two things together, Dynamic Programming should immediately come to mind.

The key insight: we're not looking for which path is best, we're counting how many paths exist. That's an additive structure, not an optimization. Greedy won't work here, and sorting won't help either. What we need is a way to systematically count without re-doing work.

That's DP.

3. Start With Brute Force to Build Intuition

The most natural first instinct is recursion. At every cell, the robot has at most two choices: go right or go down. So you explore both branches and sum the results.

int countPaths(int i, int j, int m, int n) {
    if (i == m - 1 && j == n - 1) return 1;  // reached destination
    if (i >= m || j >= n) return 0;         // out of bounds

    return countPaths(i + 1, j, m, n) + countPaths(i, j + 1, m, n);
}

This works correctly. But let's think about what it's doing.

For a 3×7 grid, the recursion tree explodes. The same subproblem - "how many paths from cell (2, 3)?" - gets computed dozens of times. You're doing redundant work on a massive scale.

Time complexity: Exponential — roughly O(2^(m+n))

Space complexity: O(m + n) recursion depth

This is too slow, but it shows us something important: the subproblems overlap. That's the exact condition under which memoization or DP pays off.

4. Brainstorm More Solutions

Step 1: Memoization - Fix the Brute Force

The simplest improvement is to cache results. If we've already computed "how many paths from (i, j)?", we store it so we don't have to recompute.

int countPaths(int i, int j, int m, int n, int[][] memo) {
    if (i == m - 1 && j == n - 1) return 1;
    if (i >= m || j >= n) return 0;
    if (memo[i][j] != 0) return memo[i][j];

    memo[i][j] = countPaths(i + 1, j, m, n, memo)
               + countPaths(i, j + 1, m, n, memo);
    return memo[i][j];
}

Now each cell is computed exactly once. Time complexity drops to O(m × n), while space complexity is O(m × n) for the memo table plus O(m + n) for the call stack.

This is a solid solution. But let's think about whether we can do better. Can we understand the problem more deeply?

Step 2: Flip the Perspective - Bottom-Up 2D DP

Memoization is top-down: we start at the destination and work backward. But with memoizaiton and DP, there's usually an alternative: start at the origin and build forward.

Let's ask ourself the question: for any cell (i, j), where could the robot have come from?

There are only two possibilities:

• From the cell directly above: (i-1, j)

• From the cell directly to the left: (i, j-1)

That gives us a clean recurrence:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Now we need some base cases. Are there any cells that where the answer is obvious? We know there's only one path for the start cell, so we can fill in 1 for cell dp[0][0]. Can we extend that?

Let's look at the whole first row: immediately we see that every cell in the top row can only be reached by moving right from the start, which means there's exactly one way to reach each of them. The same logic applies for the first column - you can only move down.

So our base cases are:

• dp[0][j] = 1 for all j (entire first row)

• dp[i][0] = 1 for all i (entire first column)

Now to confirm our logic, let's trace through a 3×3 grid to make this concrete:

Initial (base cases):
1  1  1
1  0  0
1  0  0

Fill in row by row:
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3

dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

Final grid:
1  1  1
1  2  3
1  3  6

Answer: 6. We can manually verify this is correct for a 3×3 grid.

Time: O(m × n).

Space: O(m × n).

Step 3: Notice the Redundancy - 1D Space Optimization

Now let's think about optimization. For a DP question, that often means asking ourselves: do we really need the whole DP array/grid? Or can we get away with storing fewer variables?

Let's look at the recurrence again:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

When computing row i, we only ever look at two spots: row i-1 (directly above) and cell immediately to the left of the current row. We never look at rows i-2, i-3, etc.

That means we don't need to store the entire grid. We only need one row at a time.

Here's the key insight: if we process cells left-to-right and update in place, then at the moment we compute dp[j]:

• dp[j]  still holds the value from the previous row (the "from above" contribution)

• dp[j-1]  has already been updated for the current row (the "from left" contribution)

So, dp[j] = dp[j] + dp[j-1] allows us to compute our answer with no extra storage needed.

Let's trace this for the same 3×3:

Start: dp = [1, 1, 1]   ← base case: all 1s

Row 1 (i=1):
  j=1: dp[1] = dp[1] + dp[0] = 1 + 1 = 2  →  dp = [1, 2, 1]
  j=2: dp[2] = dp[2] + dp[1] = 1 + 2 = 3  →  dp = [1, 2, 3]

Row 2 (i=2):
  j=1: dp[1] = dp[1] + dp[0] = 2 + 1 = 3  →  dp = [1, 3, 3]
  j=2: dp[2] = dp[2] + dp[1] = 3 + 3 = 6  →  dp = [1, 3, 6]

Answer: dp[2] = 6 ✓

Time: O(m × n).

Space: O(n). Same speed, a fraction of the memory.

Step 4: Is There a Mathematical Solution?

Mathematical solutions are elegant but difficult to identify in an interview setting. For this question, there is a mathematical solution, and it's worth knowing about even if you wouldn't actually reach for it first in an interview.

Think about what any valid path looks like. The robot always makes exactly (m-1) moves down and (n-1) moves right, for a total of (m+n-2) moves. The question becomes: in how many ways can you arrange those moves?

That's a combinations problem: choose which (m-1) of the (m+n-2) total moves will be "down." The rest are automatically "right."

Answer = C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)

For the 3×3 case: C(4, 2) = 6.

This runs in O(m+n) time and O(1) space. In an interview, you'd likely want to mention this after presenting the DP solution. It demonstrates mathematical depth and shows you're thinking beyond the standard template. But you still want to demonstrate your ability to think through the algorithmic solutions first.

5. Trade-Offs at a Glance

Approach	Time	Space	Notes
Brute-force recursion	O(2^(m+n))	O(m+n)	Too slow; good for building intuition
Memoized recursion	O(m × n)	O(m × n)	Intuitive; has call stack overhead
2D bottom-up DP	O(m × n)	O(m × n)	Clean and easy to trace
1D optimized DP	O(m × n)	O(n)	Best general solution
Combinatorics	O(m+n)	O(1)	Elegant; risk of overflow on large inputs

In an interview, implement the 1D DP. Mention the combinatorics solution as a bonus.

6. Write Pseudocode First

initialize dp array of size n, all set to 1

for each row i from 1 to m-1:
    for each column j from 1 to n-1:
        dp[j] = dp[j] + dp[j-1]

return dp[n-1]

This captures the entire algorithm in five lines. Get comfortable with it before writing real code.

7. Consider Edge Cases

Think through these before and after writing your solution:

• m = 1 or n = 1: Only one path exists. The DP handles this already. The inner loop never executes, and dp[n-1] stays 1.

• m = 1, n = 1: One cell, one "path" (do nothing). Our solution returns 1.

• Large inputs: m = 100, n = 100, which means the answer is astronomically large. For the combinatorics approach, you'd need to handle overflow carefully. The DP approach is fine in Java since the problem constraints are usually small enough for int variables.

  
  

8. Full Solution

public class UniquePaths {

    public static int uniquePaths(int m, int n) {
        int[] dp = new int[n];

        // Base case: first row is all 1s
        for (int j = 0; j < n; j++) {
            dp[j] = 1;
        }

        // Fill remaining rows
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // dp[j] = (paths from above) + (paths from left)
                dp[j] = dp[j] + dp[j - 1];
            }
        }

        return dp[n - 1];
    }
}

9. Test Your Solution

System.out.println(uniquePaths(1, 1));   // 1  — single cell
System.out.println(uniquePaths(1, 5));   // 1  — single row
System.out.println(uniquePaths(5, 1));   // 1  — single column
System.out.println(uniquePaths(2, 2));   // 2  — simplest non-trivial case
System.out.println(uniquePaths(3, 3));   // 6  — traced manually above
System.out.println(uniquePaths(3, 7));   // 28
System.out.println(uniquePaths(10, 10)); // 48620

10. Key Lessons for Future Problems

• Ask where each state comes from. In this problem, every cell can only be reached from above or from the left. That single observation unlocks the entire solution.

• Counting is additive, not greedy. Whenever a problem asks "how many ways," your instinct should be: define a state, find its recurrence, add up contributions. Don't try to greedily pick one path.

• Memoization and bottom-up DP solve the same problem differently. Memoization is easier to derive (just cache the recursion). Bottom-up is often cleaner and avoids stack overhead. Know both.

• Look for space optimization once the recurrence is clear. If row i only depends on row i-1, you can compress to one row. This pattern appears constantly.

• Know the mathematical alternative. Many counting problems on grids have a closed-form combinatorics solution. It won't always apply, but recognizing when it does signals strong fundamentals.

Unique Paths is less about the robot and more about learning to think in grids, a skill that compounds across dozens of interview problems.

Good Luck and Happy Coding!