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

The problem can be solved using dynamic programming. We can represent the grid as a 2D array dp where dp[i][j] represents the number of unique paths to reach cell (i, j).

1. Base Case: The number of paths to reach the starting cell (0, 0) is 1. Therefore, dp[0][0] = 1.

2. Initialization: Initialize the first row and first column of dp. Since the robot can only move down or right, there's only one path to reach any cell in the first row or first column. Thus, dp[i][0] = 1 for all i and dp[0][j] = 1 for all j.

3. Iteration: Iterate through the rest of the grid. For each cell (i, j), the number of unique paths to reach it is the sum of the number of paths to reach the cell above it (i-1, j) and the cell to its left (i, j-1). Therefore, dp[i][j] = dp[i-1][j] + dp[i][j-1].

4. Result: The number of unique paths to reach the bottom-right cell (m-1, n-1) is stored in dp[m-1][n-1].

Explanation

The dynamic programming approach avoids redundant calculations. Instead of recursively exploring all possible paths (which would be very inefficient), it builds up a table of solutions to subproblems. Each cell in the dp array represents a subproblem: "How many ways are there to reach this cell?". By solving these subproblems iteratively, we efficiently find the solution to the main problem.

Code (Java)

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

        // Base case
        dp[0][0] = 1;

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

        // Iterate and fill the dp array
        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 entire m x n grid 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 and updating it iteratively.