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 to Solve

1. Base Cases: If either m or n is 1, there's only one path.
2. Recursive Approach (Inefficient): We can recursively explore paths. From a cell (i, j), we can move right to (i, j+1) or down to (i+1, j). The total paths to (i,j) are the sum of paths to (i-1, j) and (i, j-1). However, this will lead to repeated calculations, resulting in exponential time complexity.
3. Dynamic Programming: To avoid redundant calculations, we use dynamic programming. We create a 2D array dp of size m x n to store the number of paths to reach each cell.
4. Initialization: Initialize the first row and first column of dp to 1, as there's only one way to reach any cell in the first row or column.
5. Iteration: Iterate through the dp array, calculating the number of paths to each cell (i, j) by summing the paths from the cell above (i-1, j) and the cell to the left (i, j-1).
6. Result: The value at dp[m-1][n-1] will represent the total number of unique paths to reach the bottom-right corner.

Explanation

The dynamic programming approach efficiently solves the problem by building a table of solutions to subproblems. Each cell in the dp array stores the number of unique paths to reach that specific cell. By iteratively filling the dp array, we avoid recalculating the number of paths to the same cell multiple times. The final answer is simply the value at the bottom-right cell of the dp array.

Code (C#)

public class Solution {
    public int UniquePaths(int m, int n) {
        int[,] dp = new int[m, n];

        // Initialize first row and column
        for (int i = 0; i < m; i++) {
            dp[i, 0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0, j] = 1;
        }

        // Fill the dp array using dynamic programming
        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];
            }
        }

        return dp[m - 1, n - 1];
    }
}

Complexity Analysis

• Time Complexity: O(m * n). We iterate through the m x n DP array once.
• Space Complexity: O(m * n). We use a 2D array of size m x n to store the DP table. This could be optimized to O(min(m,n)) by using only a 1D array if desired.