Unique Paths Problem

Problem Description

Given a robot on an m x n grid, find the number of unique paths the robot can take from the top-left corner to the bottom-right corner. The robot can only move down or right.

Brute Force Approach (Recursion)

A naive approach is to use recursion to explore all possible paths. Start at the top-left corner and recursively call the function for the 'down' and 'right' movements. When the bottom-right corner is reached, increment the count.

Code (Python):

def unique_paths_recursive(m, n):
    if m == 1 or n == 1:
        return 1
    return unique_paths_recursive(m - 1, n) + unique_paths_recursive(m, n - 1)

Time Complexity: O(2^(m+n)). This is because each call branches into two more calls, leading to exponential growth.

Space Complexity: O(m+n). This represents the maximum depth of the recursion tree.

This approach is highly inefficient and will result in a "Time Limit Exceeded" error for larger inputs.

Optimal Approach (Dynamic Programming)

A more efficient approach is to use dynamic programming. Create a 2D array dp of size m x n, where dp[i][j] represents the number of unique paths to reach cell (i, j). Fill the array using the following logic:

1. Initialize the first row and first column to 1, since there's only one way to reach any cell in the first row or column.
2. For the remaining cells, dp[i][j] = dp[i-1][j] + dp[i][j-1], since we can reach (i, j) either from above or from the left.

Code (Python):

def unique_paths_dp(m, n):
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

Time Complexity: O(m*n). We iterate through each cell in the m x n grid once.

Space Complexity: O(m*n). We use a 2D array of size m x n to store the number of unique paths.

Improved Space Complexity (Dynamic Programming): We can optimize the space complexity to O(min(m, n)) by storing only the previous row/column. Since each dp[i][j] depends only on the values immediately above and to the left, it is sufficient to keep track of the previous row.

Code (Python):

def unique_paths_dp_optimized(m, n):
    if m < n:
        m, n = n, m  # Ensure m >= n
    
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
            
    return dp[n-1]

Time Complexity: O(m*n). Still iterates through the m x n grid.

Space Complexity: O(n). Only stores one row of length n.

Edge Cases:

• If either m or n is 1, there is only one path.
• m and n are both greater than 0.

Summary

The optimal solution is using dynamic programming with an optimized space complexity of O(min(m, n)). This approach avoids redundant calculations by storing and reusing intermediate results, leading to a significant performance improvement over the brute-force recursive approach.