Unique Paths Problem

Problem Statement:

Given a grid of size m x n, you need to find the number of unique paths from the top-left corner to the bottom-right corner. You can only move either down or right at any point in time.

---

Solution Explanation

calc Function

The calc function recursively computes the number of unique paths from a given cell (i, j) in the grid to the bottom-right corner (m-1, n-1).

Steps:

1. Base Case (Reaching the Bottom-Right Corner):

   • If the current cell (i, j) is the bottom-right corner (m-1, n-1), return 1 because there's exactly one unique path (the path where you are already at the destination).

2. Out of Bounds Case:

   • If the current cell (i, j) is outside the grid boundaries (i.e., i >= m or j >= n), return 0 since there are no valid paths from this point.

3. Memoization Check:

   • Before proceeding with the recursive calculation, check if the number of paths from the current cell (i, j) has already been computed and stored in dp[i][j]. If dp[i][j] is not -1, return the cached value to avoid redundant calculations and improve efficiency.

4. Recursive Calculation:

   • Calculate the number of paths by recursively calling calc for the right and down cells:
     • Right: calc(i, j+1) (move right)
     • Down: calc(i+1, j) (move down)
   • The sum of these two values gives the total number of unique paths from the current cell (i, j).
   • Store this result in dp[i][j] for future use.

---

uniquePaths Function

The uniquePaths function initializes the memoization array and starts the recursive calculation from the top-left corner (0, 0).

Steps:

1. Initialization of DP Array:

   • Create a 2D vector dp of size (m+1) x (n+1) initialized with -1. This 2D array will store the number of unique paths from each cell. The extra row and column are included to handle boundary conditions more gracefully.

2. Initial Call to calc:

   • Start the recursion from the top-left corner (0, 0) by calling the calc function.

3. Special Case for 1x1 Grid:

   • If the grid size is 1x1, return the result directly (which is 1, as there is only one cell).

4. Return the Result:

   • After the recursion, return the number of unique paths stored in dp[0][0], which represents the top-left cell.

---

Test Cases

Test Case 1: Basic Case

Input:
m = 3, n = 2

Output:
3

Explanation:
There are 3 unique paths from the top-left to the bottom-right corner in a 3x2 grid:

1. Move right, move right, move down.
2. Move right, move down, move right.
3. Move down, move right, move right.

---

Test Case 2: Single Row Grid

Input:
m = 1, n = 5

Output:
1

Explanation:
In a 1x5 grid, there is only one path: move right repeatedly.

---

Test Case 3: Single Column Grid

Input:
m = 6, n = 1

Output:
1

Explanation:
In a 6x1 grid, there is only one path: move down repeatedly.

---

Test Case 4: Square Grid

Input:
m = 4, n = 4

Output:
20

Explanation:
There are 20 unique paths from the top-left to the bottom-right corner in a 4x4 grid.

---

Test Case 5: Large Grid

Input:
m = 10, n = 10

Output:
48620

Explanation:
The number of unique paths for a 10x10 grid is 48620.

---

Time Complexity:

• Recursive Calls: The time complexity is reduced due to memoization. The recursion explores each cell in the grid only once.
• Overall Time Complexity: O(m * n), where m and n are the number of rows and columns in the grid.

Space Complexity:

• Space Complexity: O(m * n) for storing the memoization array.

— Written by Saurabh Patil • B.Tech CSE • Software Developer