Description:
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
Examples:
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 -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> DownSolution in Python:
To solve the problem of finding the number of unique paths the robot can take to reach the bottom-right corner of an m x n grid, we can use a dynamic programming approach.
Steps to Solve the Problem:
- Define the Problem in Terms of Subproblems:
- We need to calculate the number of ways to reach each cell
(i, j)from the starting cell(0, 0). - The robot can only move right or down, so the number of ways to reach cell
(i, j)is the sum of the number of ways to reach cell(i-1, j)(from the cell above) and cell(i, j-1)(from the cell to the left).
- We need to calculate the number of ways to reach each cell
- Initialize the Base Cases:
- The number of ways to reach any cell in the first row
(0, j)is1because the robot can only move right. - Similarly, the number of ways to reach any cell in the first column
(i, 0)is1because the robot can only move down.
- The number of ways to reach any cell in the first row
- Fill the DP Table:
- Create a 2D array
dpwheredp[i][j]represents the number of unique paths to cell(i, j). - Iterate through the grid, and for each cell
(i, j), updatedp[i][j]based on the values from the cell above it and the cell to the left of it.
- Create a 2D array
- Return the Result:
- The value at
dp[m-1][n-1]will give us the number of unique paths to the bottom-right corner of the grid.
- The value at
Python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# Create a 2D array 'dp' with dimensions m x n, initialized to 0
dp = [[0] * n for _ in range(m)]
# Initialize the first row and first column
for i in range(m):
dp[i][0] = 1 # There is only one way to reach cells in the first column (move down)
for j in range(n):
dp[0][j] = 1 # There is only one way to reach cells in the first row (move right)
# Fill the dp table
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Return the number of unique paths to reach the bottom-right corner
return dp[m-1][n-1]Detailed Explanation:
- Initialization:
dp = [[0] * n for _ in range(m)]creates anm x ngrid initialized to0.- The loops
for i in range(m): dp[i][0] = 1andfor j in range(n): dp[0][j] = 1set the first row and first column to1since there is only one way to reach any of these cells.
- Filling the DP Table:
- The nested loop
for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1]computes the number of ways to reach each cell(i, j)by summing the ways to reach the cell from above (dp[i-1][j]) and from the left (dp[i][j-1]).
- The nested loop
- Result:
return dp[m-1][n-1]returns the value at the bottom-right corner of the grid, which represents the number of unique paths to that cell.
This approach ensures that we efficiently compute the number of unique paths using dynamic programming in O(m * n) time complexity, which is suitable given the problem constraints.
Solution in Javascript:
JavaScript
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
// Create a 2D array 'dp' with dimensions m x n, initialized to 0
let dp = Array.from({ length: m }, () => Array(n).fill(0));
// Initialize the first row and first column
for (let i = 0; i < m; i++) {
dp[i][0] = 1; // There is only one way to reach cells in the first column (move down)
}
for (let j = 0; j < n; j++) {
dp[0][j] = 1; // There is only one way to reach cells in the first row (move right)
}
// Fill the dp table
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
// Return the number of unique paths to reach the bottom-right corner
return dp[m-1][n-1];
};Solution in Java:
Java
class Solution {
public int uniquePaths(int m, int n) {
// Create a 2D array 'dp' with dimensions m x n, initialized to 0
int[][] dp = new int[m][n];
// Initialize the first row and first column
for (int i = 0; i < m; i++) {
dp[i][0] = 1; // There is only one way to reach cells in the first column (move down)
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1; // There is only one way to reach cells in the first row (move right)
}
// Fill the dp table
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 the number of unique paths to reach the bottom-right corner
return dp[m-1][n-1];
}
}Solution in C#:
C#
public class Solution {
public int UniquePaths(int m, int n) {
// Create a 2D array 'dp' with dimensions m x n, initialized to 0
int[,] dp = new int[m, n];
// Initialize the first row and first column
for (int i = 0; i < m; i++) {
dp[i, 0] = 1; // There is only one way to reach cells in the first column (move down)
}
for (int j = 0; j < n; j++) {
dp[0, j] = 1; // There is only one way to reach cells in the first row (move right)
}
// Fill the dp table
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 the number of unique paths to reach the bottom-right corner
return dp[m-1, n-1];
}
}