NUHMAN.com

Introduction

LeetCode 62: Unique Paths is a dynamic programming problem that asks you to calculate the number of unique paths to travel from the top-left corner to the bottom-right corner of a grid, moving only down or right at any point.

This problem requires you to efficiently count all the ways to reach the destination, considering constraints like grid size and movement restrictions. It's a good example of how dynamic programming can be used to solve combinatorics problems.

Problem Statement

A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. How many possible unique paths are there to reach the bottom-right corner?

Example 1:

go

Input: m = 3, n = 7
Output: 28

Example 2:

go

Input: m = 3, n = 2
Output: 3

Constraints

• 1 <= m, n <= 100
• The answer is guaranteed to be less than or equal to 2 * 10^9.

Approach: Dynamic Programming

The problem can be approached using dynamic programming. The idea is to break the problem down into smaller subproblems, where each subproblem represents the number of ways to reach a certain point in the grid.

1. Grid Setup: We can represent the grid as a 2D matrix where each cell (i, j) will store the number of ways to reach that cell from the top-left corner (0, 0).
2. Base Case: There's only one way to reach any cell in the first row or first column, which is to move only right or only down.
3. Recurrence Relation: For each cell (i, j), the number of ways to reach it is the sum of the number of ways to reach the cell directly above it and the number of ways to reach the cell directly to the left of it:
4. dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]
5. Final Answer: The value in the bottom-right corner (m-1, n-1) will give the total number of unique paths.

Go Implementation

go

func uniquePaths(m int, n int) int {
    // Create a 2D array with all elements initialized to 1
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    // Base cases: Fill the first row and the first column with 1
    for i := 0; i < m; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }

    // Fill the rest of the grid using the recurrence relation
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }

    return dp[m-1][n-1]  // Return the value in the bottom-right corner
}

Example Walkthrough

For input m = 3 and n = 7, we want to calculate the number of unique paths from the top-left corner (0, 0) to the bottom-right corner (2, 6).

Step-by-step Explanation:

1. Initialize the DP table: The table starts with all cells initialized to 1:

lua

dp = [[1, 1, 1, 1, 1, 1, 1],
      [1, 0, 0, 0, 0, 0, 0],
      [1, 0, 0, 0, 0, 0, 0]]

1. Fill the first row and first column with 1 since there's only one way to reach any cell in the first row (move right) or the first column (move down):

lua

dp = [[1, 1, 1, 1, 1, 1, 1],
      [1, 0, 0, 0, 0, 0, 0],
      [1, 0, 0, 0, 0, 0, 0]]

1. Apply the recurrence relation to fill the rest of the grid:

lua

dp = [[1, 1, 1, 1, 1, 1, 1],
      [1, 2, 3, 4, 5, 6, 7],
      [1, 3, 6, 10, 15, 21, 28]]

1. Final Answer: The bottom-right corner value dp[2][6] = 28, meaning there are 28 unique paths.

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(m * n)

• Time Complexity: The algorithm needs to fill a m x n DP table, resulting in a time complexity of O(m * n).
• Space Complexity: The space complexity is also O(m * n) because we are storing the results for all subproblems in a 2D array.

Optimizing Space Complexity

We can optimize the space complexity to O(n) by storing only the current row and the previous row at any point in time, since the current state only depends on the current row and the row directly above it.

Here is the optimized approach:

go

func uniquePaths(m int, n int) int {
    // Use a 1D array for dynamic programming
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[j] += dp[j-1]  // Update the current cell with the sum of the top and left cells
        }
    }

    return dp[n-1]
}

In this optimized approach:

• We only store the current row in a 1D array dp.
• The space complexity is reduced to O(n).

Edge Cases

• Small grids: For grids like 1x1, the result is always 1 because there’s only one possible path.
• Single row or single column: If m = 1 or n = 1, there’s only one way to traverse the grid (either all the way down or all the way right).
• Large grids: The solution works efficiently even for large grids, as long as m and n are within the problem's constraints.

Key Takeaways

• Dynamic Programming allows us to break the problem into subproblems and compute the number of unique paths efficiently.
• Space Optimization: By using only a 1D array to store intermediate results, we reduce the space complexity significantly.
• This problem is a classic example of using recurrence relations to solve combinatorics problems efficiently.