What is the Unique Paths Problem?

The Unique Paths Problem centers around navigating a grid, specifically from the top-left corner to the bottom-right corner of an m x n grid while only being able to move either right or down. The challenge is to calculate how many distinct paths are available to reach the destination.

Problem Statement:

Given a grid with m rows and n columns, how many unique paths exist from the start cell (0, 0) to the end cell (m-1, n-1)?

For example, consider a grid with dimensions 3 x 2:

[ . , . ]
[ . , . ]
[ . , . ]

The valid paths to get from the top-left to the bottom-right are:

1. Down -> Down -> Right
2. Down -> Right -> Down
3. Right -> Down -> Down
4. Right -> Right -> Down
5. Down -> Down -> Right

In total, there are 3 unique paths for a 3 x 2 grid.

Naive Approach

Before diving into dynamic programming, let's briefly touch on the naive recursive approach to solving this problem. The recursive function would traverse the grid and explore each valid path starting from dp(i, j), where i is the current row and j is the current column.

Recursive Function:

def uniquePaths(m: int, n: int) -> int:
    if m == 1 or n == 1:  # Base case
        return 1
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)  # Move down and right

While this approach is straightforward, it has exponential time complexity, as it explores the same paths multiple times. For larger grids, this method becomes inefficient.

Dynamic Programming Approach

To optimize the solution, we employ dynamic programming (DP). DP allows us to store intermediate results, thus avoiding redundant calculations.

DP Table:

We can use a 2D list (matrix) dp to store the number of ways to reach each position in the grid. The value dp[i][j] will represent the number of unique paths to reach cell (i, j).

Transition Formula:

The number of unique paths to reach a cell is the sum of unique paths to reach the cell directly above it and the cell to the left. Therefore, the formula becomes:

dp[i][j] = dp[i-1][j] + dp[i][j-1]  

Where:

• dp[i-1][j] is the cell above
• dp[i][j-1] is the cell to the left

Base Case:

• The first row and the first column can only be reached in one way (all moves to the right or all moves downward):

dp[0][j] = 1 for all j
dp[i][0] = 1 for all i  

Implementation:

Here’s how we can implement this in Python:

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]  # Create a m x n grid with all cells initialized to 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]  # Return the value at the bottom-right corner

Time and Space Complexity:

• Time Complexity: O(m * n) because we fill each cell of the m x n grid once.
• Space Complexity: O(m * n) due to the space used by the dp array.

Optimization:

An even more space-efficient solution can be achieved by noting that the calculation of the current row only requires the current row and the previous row. This means you can reduce the space complexity to O(n) by eliminating the need for a full m x n grid:

Optimized Implementation:

def uniquePaths(m: int, n: int) -> int:
    dp = [1] * n  # Only keep one row

    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]  # Update the current cell based on the previous row

    return dp[-1]  # Return the last element in dp which represents the last cell

Utilizing this approach, we maintain the O(m * n) time complexity while reducing the space complexity to O(n).

Final Thoughts on Unique Paths

The Unique Paths Problem is not just a test of dynamic programming skills; it elegantly demonstrates how breaking down complex problems into manageable parts can lead to efficient solutions. From visualization of the grid to implementing the DP approach, tackling this problem enhances your algorithmic thinking and prepares you for similar challenges in dynamic programming contexts.