Leetcode 62. Unique Paths

 62. Unique Paths

Medium, Dynamic Programming

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.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= m, n <= 100

The Unique Paths problem asks to find the number of distinct paths a robot can take to move from the top-left corner to the bottom-right corner of an m x n grid, where the robot can only move either down or right.

Understanding the Problem:

Given the constraints:

• The robot starts at the top-left corner (0, 0) and needs to reach the bottom-right corner (m-1, n-1).
• The robot can move only right or down.
• The task is to calculate how many unique paths exist from the starting point to the destination.

Approach 1: Dynamic Programming

Explanation:

Dynamic programming (DP) is a suitable approach for this problem. At each point in the grid, the number of ways to reach that point can be calculated by adding the number of ways to reach the point directly above it and the number of ways to reach the point directly to its left.

For a grid of size m x n:

• dp[i][j] will represent the number of unique paths to reach cell (i, j).
• The base case is that there is only one way to get to any point in the first row or the first column, which is by moving all the way across that row or column (since the robot can only move down or right).

The general recurrence relation is:

• dp[i][j] = dp[i-1][j] + dp[i][j-1]
  • Where dp[i-1][j] is the number of ways to reach from above and dp[i][j-1] is the number of ways to reach from the left.

Steps:

1. Initialize a DP array dp where dp[i][j] will store the number of unique paths to reach that cell.
2. Fill the base cases:
   • For the first row and the first column, there's only one way to reach each cell (by moving all the way right or down).
3. For each remaining cell, calculate the number of ways to reach it using the recurrence relation.
4. The final answer will be stored in dp[m-1][n-1].

Code:

public class Solution {
    public int UniquePaths(int m, int n) {
        int[,] dp = new int[m, n];
        
        // Initialize the first row and the first column
        for (int i = 0; i < m; i++) {
            dp[i, 0] = 1; // There's only one way to reach any cell in the first column (downward)
        }
        for (int j = 0; j < n; j++) {
            dp[0, j] = 1; // There's only one way to reach any cell in the first row (rightward)
        }
        
        // Fill the DP table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i, j] = dp[i-1, j] + dp[i, j-1]; // sum the ways from top and left
            }
        }
        
        return dp[m-1, n-1]; // The number of ways to reach the bottom-right corner
    }
}

Time Complexity:

• Time Complexity: $O(m \times n)$, since we fill a DP table of size m x n.
• Space Complexity: $O(m \times n)$, because we use a DP table of size m x n.

---

Approach 2: Combinatorics (Mathematical Approach)

Explanation:

This problem can also be solved combinatorially. The robot must take a total of $m - 1$ steps down and $n - 1$ steps right to reach the bottom-right corner from the top-left. The total number of steps will be $m + n - 2$, and we need to choose $m - 1$ (or equivalently $n - 1$) steps to go down (the rest will be right).

The number of unique ways to select $m - 1$ down steps (or equivalently $n - 1$ right steps) from a total of $m + n - 2$ steps is given by the binomial coefficient:

$$C(m + n - 2, m - 1) = \frac{(m+n-2)!}{(m-1)! \times (n-1)!}$$

Code (using factorials):

public class Solution {
    public int UniquePaths(int m, int n) {
        long result = 1;
        
        // Calculate the binomial coefficient C(m + n - 2, m - 1)
        for (int i = 1; i < m; i++) {
            result = result * (n + i - 1) / i;
        }
        
        return (int)result;
    }
}

Time Complexity:

• Time Complexity: $O(m)$, since we loop from 1 to $m-1$ to compute the binomial coefficient.
• Space Complexity: $O(1)$, as we use only a few variables for the calculation.

---

Comparison of Approaches:

Approach	Time Complexity	Space Complexity	Explanation
Dynamic Programming	$O(m \times n)$	$O(m \times n)$	Fills a DP table to count unique paths.
Combinatorics	$O(m)$	$O(1)$	Uses binomial coefficients to compute the answer.

---

Summary:

• Dynamic Programming is straightforward and works efficiently for moderate values of m and n.
• Combinatorics provides a more optimized solution in terms of space complexity and may be faster for larger grids, especially when m and n are large.

Let me know if you need further clarification or additional approaches!