Problem Statement:

A robot is located at the top-left corner of a m x n grid and needs to reach the bottom-right corner. 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 which is exactly (m, n). How many possible unique paths are there for the robot to reach this corner?

Approach:

This is a classic dynamic programming problem that can be solved by creating a 2D array to keep track of the number of unique paths to reach each cell.

We can start with initializing the first row and the first column to 1, as the robot can only move either down or right from these cells. Then, we can fill in the remaining cells of the grid using the formula:

grid[i][j] = grid[i-1][j] + grid[i][j-1]

This formula works because to reach cell (i,j), the robot can either come from the top (i-1, j) or the left (i, j-1). So the number of unique paths to reach cell (i,j) is equal to the sum of the number of unique paths to reach these two cells.

Finally, the number of unique paths to reach the bottom-right corner (m,n) can be found in the last cell of the grid, i.e. grid[m-1][n-1].

Code:

def uniquePaths(m: int, n: int) -> int: grid = [[0]*n for _ in range(m)]

# initialize first row and first column to 1
for i in range(m):
    grid[i][0] = 1
for j in range(n):
    grid[0][j] = 1
    
# fill in the remaining cells using the dynamic programming formula
for i in range(1,m):
    for j in range(1,n):
        grid[i][j] = grid[i-1][j] + grid[i][j-1]
        
# return the number of unique paths to the bottom-right corner
return grid[m-1][n-1]

Example:

Input: m = 3, n = 7

Output: 28

Explanation: There are 28 unique paths from top-left corner to bottom-right corner in a 3x7 grid.

Time Complexity: O(mn) Space Complexity: O(mn)

1