Unique Paths medium

Problem Statement

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Steps

1. Base Cases: If either m or n is 1, there's only one path.

2. Recursive Approach (Inefficient): We can recursively explore all possible paths. This approach is highly inefficient due to repeated calculations.

3. Dynamic Programming Approach (Efficient): We'll use a DP table dp of size m x n to store the number of paths to reach each cell. dp[i][j] will represent the number of paths to reach cell (i, j).

   • Initialize dp[0][0] = 1 (one path to reach the starting cell).
   • Initialize the first row and first column of dp to 1 (only one way to reach any cell in the first row or column).
   • Iterate through the remaining cells of dp. The number of paths to reach dp[i][j] is the sum of paths to reach dp[i-1][j] (from above) and dp[i][j-1] (from the left). This is because the robot can only move down or right.
   • The final result is dp[m-1][n-1].

4. Space Optimization: We can optimize space by using only a 1D array instead of a 2D array.

Explanation

The dynamic programming approach avoids redundant calculations by storing the results of subproblems. Each cell's value depends only on its top and left neighbors. By building up the solution from the top-left corner, we efficiently compute the number of unique paths. The space optimization further reduces memory usage by reusing the same 1D array.

Code (C++)

#include <vector>

using namespace std;

int uniquePaths(int m, int n) {
    // Space-optimized DP solution
    vector<int> dp(n, 1); // Initialize first row

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[j] += dp[j - 1];
        }
    }

    return dp[n - 1];
}

Complexity

• Time Complexity: O(m*n). We iterate through the DP table once.
• Space Complexity: O(n). We use a 1D DP array of size n. The space-optimized approach reduces the space complexity compared to a 2D array solution which would be O(m*n).