Problem Statement

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Input: m = 3, n = 2 
Output: 3 
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down 

class Solution {
    int rowL = 0;
    int columnL = 0;
    int cache[][];
    public int uniquePaths(int m, int n) {
        cache = new int[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                cache[i][j] = -1;
            }
        }
        rowL= m;
        columnL = n;
        return travel(0,0);
    }
    public int travel(int row, int column) {
        if(row >= rowL || column >= columnL) {
            return 0;
        }
        if(row == rowL-1 && column == columnL - 1) {
            return 1;
        }
        if(cache[row][column] != -1) {
            return cache[row][column];
        }
        cache[row][column] = travel(row+1, column) + travel(row, column+1);
        return cache[row][column];
    }
}

Breaking Down the Solution

1. Initialization: The solution initializes a 2D array called cache to store intermediate results. The values in this array are initially set to -1 to indicate that they haven’t been computed yet.
2. Recursive Function: The heart of the solution lies in the travel function. This function recursively explores the grid while keeping track of the number of unique paths.
3. Base Cases: The function checks for two base cases:
   • If the current position is outside the grid boundaries, it returns 0 (indicating no path).
   • If the current position is the destination (bottom-right corner), it returns 1 (indicating one unique path).
4. Memoization: Before making a recursive call, the function checks if the result for the current position has already been computed and stored in the cache. If so, it retrieves the result from there, avoiding redundant calculations.
5. Recursive Calls: If the result is not in the cache, the function makes two recursive calls: one for moving down (travel(row+1, column)) and another for moving right (travel(row, column+1)). It then adds these results together and stores the sum in the cache.
6. Returning the Result: Finally, the function returns the computed result, which represents the total number of unique paths to reach the destination.

Efficiency Through Dynamic Programming

By using dynamic programming and memoization, this solution significantly optimizes the computation of unique paths, especially for large grids. It avoids recalculating the same subproblems repeatedly and leverages the results stored in the cache.

The “Unique Paths” problem is just one example of how dynamic programming can be a powerful tool for solving complex algorithmic challenges efficiently. It showcases how breaking a problem down into smaller, overlapping subproblems and storing their results can lead to elegant and optimized solutions.

Problem Statement: https://leetcode.com/problems/unique-paths/