Unique Paths

Recursion → Memoization → DP Intuition

Given an m x n grid, a robot starts at the top-left corner and can only move right or down. Find the total number of unique paths to reach the bottom-right corner.

Brute Force (Recursion)

Intuition

At every cell, we have only two choices:

• Move Right
• Move Down

So, the total paths from the current cell are:

paths = right + down

We recursively explore both possibilities until we reach the destination.

Java

class Solution {

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

    private int solve(int i, int j, int m, int n) {

        if (i >= m || j >= n) return 0;

        if (i == m - 1 && j == n - 1) return 1;

        int right = solve(i, j + 1, m, n);
        int down = solve(i + 1, j, m, n);

        return right + down;
    }
}

Complexity

• Time: O(2^(m+n))
• Space: O(m+n)

The same states are solved repeatedly, causing exponential time complexity.

Better Approach (Memoization)

Intuition

Notice that:

solve(1,1)

may be called from multiple paths.

Instead of recalculating it every time, store the answer in a DP table.

Define:

dp[i][j]

as the number of ways to reach the destination from cell (i,j).

Java

class Solution {

    public int uniquePaths(int m, int n) {

        int[][] dp = new int[m][n];

        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        return solve(0, 0, m, n, dp);
    }

    private int solve(int i, int j, int m, int n, int[][] dp) {

        if (i >= m || j >= n) return 0;

        if (i == m - 1 && j == n - 1) return 1;

        if (dp[i][j] != -1) return dp[i][j];

        int right = solve(i, j + 1, m, n, dp);
        int down = solve(i + 1, j, m, n, dp);

        return dp[i][j] = right + down;
    }
}

Complexity

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

DP State Visualization

For a 3 x 3 grid:

? ? ?
? ? ?
? ? 1

Destination cell:

dp[2][2] = 1

because once we reach the destination, there is exactly one valid path.

Every other cell follows:

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

The answer is built by combining paths from the right and bottom cells.

Dry Run

Input:

m = 3
n = 2

Grid:

S .
. .
. D

Possible paths:

Right → Down → Down
Down → Right → Down
Down → Down → Right

Answer:

3

Key Takeaway

Whenever a problem asks:

• Count total ways
• Move in multiple directions
• Same states are revisited

Think:

Recursion → Memoization → DP

and define a state that represents:

"Number of ways from this position to the destination."