DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Unique Paths

#algorithms #interview #java #leetcode

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
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

may be called from multiple paths.

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

Define:

dp[i][j]
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Complexity

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

DP State Visualization

For a 3 x 3 grid:

? ? ?
? ? ?
? ? 1
Enter fullscreen mode Exit fullscreen mode

Destination cell:

dp[2][2] = 1
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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

Dry Run

Input:

m = 3
n = 2
Enter fullscreen mode Exit fullscreen mode

Grid:

S .
. .
. D
Enter fullscreen mode Exit fullscreen mode

Possible paths:

Right → Down → Down
Down → Right → Down
Down → Down → Right
Enter fullscreen mode Exit fullscreen mode

Answer:

3
Enter fullscreen mode Exit fullscreen mode

Key Takeaway

Whenever a problem asks:

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

Think:

Recursion → Memoization → DP
Enter fullscreen mode Exit fullscreen mode

and define a state that represents:

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

Top comments (0)