Solution For Unique Paths

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 3×7 grid.

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

Step by Step Implementation For Unique Paths

There are many ways to solve the unique paths problem. One way is to use a dynamic programming approach.

We can create a 2D array to store the number of unique paths from each cell to the end. Then, we can populate this array by iterating through the matrix. For each cell, we can add the number of unique paths from the cell to the right and the cell below.

After we have iterated through the entire matrix, we will have our answer stored in the last cell of the matrix.

public int uniquePaths(int m, int n) {
    
    // Create a 2D array to store the number of unique paths from each cell
    int[][] paths = new int[m][n];
    
    // Initialize the first row and column to 1 (there is only 1 way to get to the end)
    for (int i = 0; i < m; i++) {
        paths[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        paths[0][j] = 1;
    }
    
    // Iterate through the matrix, adding the number of unique paths from the cell to the right and the cell below
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            paths[i][j] = paths[i-1][j] + paths[i][j-1];
        }
    }
    
    // Return the number of unique paths stored in the last cell of the matrix
    return paths[m-1][n-1];
}

def uniquePaths(m, n): 

# This problem can be solved by using Dynamic Programming. 
# We create a 2D array with dimensions m x n to store the 
# number of unique paths from each cell to the destination. 
# Then, we initialize the first row and column of the array 
# to 1 since there is only 1 unique path to the destination 
# from any cell in the first row or column. 
# For the rest of the cells in the array, we find the number 
# of unique paths by adding the number of unique paths from 
# the cell above and to the left of the current cell. 
# This is because the only possible paths from any cell are 
# either from the cell above or from the cell to the left. 
# Therefore, the total number of unique paths from the current 
# cell is the sum of the number of unique paths from the cell 
# above and the number of unique paths from the cell to the left. 
# We can fill in the rest of the array using this approach, 
# and the number of unique paths from the top-left cell to the 
# bottom-right cell will be stored in the bottom-right cell of the array. 

# Create a 2D array with dimensions m x n 
paths = [[0 for x in range(n)] for y in range(m)] 

# Initialize the first row and column of the array 
for i in range(n): 
	paths[0][i] = 1
for j in range(m): 
	paths[j][0] = 1

# Fill in the rest of the array 
for i in range(1, m): 
	for j in range(1, n): 
		paths[i][j] = paths[i-1][j] + paths[i][j-1] 

# Return the number of unique paths from the top-left 
# cell to the bottom-right cell 
return paths[m-1][n-1]

There are a few ways to approach this problem. One way would be to use a dynamic programming approach, where you keep track of the number of unique paths to each position on the grid. Another way would be to use a combinatorial approach, where you calculate the number of ways to reach the end position using only down and right moves.

Here is a solution using the dynamic programming approach:

function uniquePaths(m, n) {

// create a 2D array to store the number of unique paths to each position

const paths = [];

for (let i = 0; i < m; i++) {

paths.push([]);

}

// initialise the number of paths to the top left corner as 1

paths[0][0] = 1;

// fill in the rest of the values in the array

for (let i = 0; i < m; i++) {

for (let j = 0; j < n; j++) {

// if we're not at the top left corner, the number of paths to the current position is the sum of the paths to the position above and to the left

if (i > 0 && j > 0) {

paths[i][j] = paths[i - 1][j] + paths[i][j - 1];

}

// if we're at the top row, the number of paths to the current position is the number of paths to the position to the left

else if (i === 0 && j > 0) {

paths[i][j] = paths[i][j - 1];

}

// if we're at the left column, the number of paths to the current position is the number of paths to the position above

else if (i > 0 && j === 0) {

paths[i][j] = paths[i - 1][j];

}

}

}

// return the number of paths to the bottom right corner

return paths[m - 1][n - 1];

}

There are many ways to solve this problem. One way is to use a dynamic programming approach, where we calculate the number of unique paths for each cell in the grid. We can do this by initializing a 2D array of size (m x n), where m is the number of rows and n is the number of columns in the grid. We then set the value of the first cell in the array to 1, since there is only 1 unique path to this cell. We then iterate through the array, calculating the number of unique paths to each cell based on the values of the cells above and to the left of it. The final value in the array will be the number of unique paths from the starting point to the end point.

Another way to solve this problem is to use a combinatorial approach. We can calculate the number of unique paths by choosing the number of steps we take in each direction (right or down). We need to take a total of m + n - 2 steps, and we can choose any combination of m - 1 steps to go right and n - 1 steps to go down. The number of unique paths will be the number of ways we can choose these steps, which is equal to (m + n - 2)! / ((m - 1)! * (n - 1)!).

There are a few different ways to solve this problem. One way is to use a dynamic programming approach.

We can create a 2D array to keep track of the number of unique paths from each cell. Then, we can populate the array using the following recurrence:

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

This means that the number of unique paths to a cell is equal to the sum of the number of unique paths to the cell above it and the cell to the left of it.

We can initialize the first row and column of the array to 1, since there is only 1 path to any cell in the first row or column. Then, we can simply return the value in the bottom-right corner of the array.

Here is the code in C#:

public int UniquePaths(int m, int n) { int[,] dp = new int[m,n]; for(int i=0; i < m; i++) { dp[i,0] = 1; } for(int j=0; j < n; j++) { dp[0,j] = 1; } 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]; }