Welcome back, fellow coders! Today, we’re diving into one of my favorite types of LeetCode problems—**Unique Paths**. This problem is a great exercise in both **recursion**, with an emphasis on **memoization** to optimize the solution.

## Problem Overview

The problem statement is simple but interesting: There is a robot on an m x n grid, starting at the top-left corner (0, 0). The robot can only move **right** or **down**, and it needs to reach the bottom-right corner (m – 1, n – 1). Our task is to find the **number of unique paths** the robot can take to reach the destination. You can read the problem in LeetCode website.

## Constraints

- The grid size is determined by two integers,
`m`

and`n`

. - The answer should not exceed 2 * 10^9.

## Approach Breakdown

### 1. Understanding the Grid and Movement

The robot can only move **right** or **down**, which simplifies the directions to be considered. This means at any point `(i, j)`

on the grid, the robot can either move:

- Down to
`(i + 1, j)`

, or - Right to
`(i, j + 1)`

.

### 2. Recursion

A straightforward recursive approach would involve trying both possible moves (right and down) at each step until we reach the bottom-right corner. At this point, we increment the path count. If we move out of bounds, we return 0.

This solution, however, leads to a lot of **redundant calculations**. For example, different paths might lead the robot to the same grid cell multiple times, forcing us to recompute the number of ways from that point over and over.

## 3. Memoization

To optimize our solution, we can store the results of subproblems, which is where **memoization** comes into play. By storing the number of unique paths from each cell in a **2D memoization array**, we avoid redundant calculations. If the robot visits the same cell through different paths, we simply retrieve the precomputed value.

## Solution Code:

`class Solution {`

public int uniquePaths(int m, int n) {

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

return move(m, n, 0, 0, memo);

}

static int move(int m, int n, int i, int j, int[][] memo) {

if (i >= m || j >= n) {

return 0; // Out of bounds

}

if (i == m - 1 && j == n - 1) {

return 1; // Reached bottom-right corner

}

if (memo[i][j] > 0) {

return memo[i][j]; // Already computed for this cell

}

// Compute number of paths from the current cell

memo[i][j] = move(m, n, i + 1, j, memo) + move(m, n, i, j + 1, memo);

return memo[i][j];

}

}

## Step-by-Step Explanation

**Base Case**: If the robot moves outside the grid, we return 0, indicating no valid path. If the robot reaches the bottom-right corner, we return 1, indicating one valid path.**Memoization Check**: Before computing the number of paths for a given cell, we check if we’ve already solved the subproblem. If so, we return the stored result.**Recursive Calls**: If no memoized result is available, we recursively explore the paths by moving down and right. The sum of these recursive calls gives the total number of paths from the current cell.

## Time Complexity

With memoization, each cell is computed at most once, resulting in a time complexity of **O(m * n)**. Without memoization, the time complexity would be exponentially larger, as we would re-explore many grid cells multiple times.

## Conclusion

The beauty of this problem lies in its ability to illustrate the power of **dynamic programming**. By breaking the problem down into smaller subproblems and storing their results, we dramatically improve the efficiency of the solution. In fact, this solution performs optimally with a time complexity of **O(m * n)** and avoids the inefficiencies of a pure recursive approach.

If you enjoyed this article and found it helpful, don’t forget to subscribe and turn on notifications for more LeetCode solutions. Happy coding!