62. Unique Paths Medium
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.
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:
- Right -> Down -> Down
- Down -> Down -> Right
- Down -> Right -> Down
Example 3:
Input: m = 7, n = 3
Output: 28
Example 4:
Input: m = 3, n = 3
Output: 6
Approach
Input: An m x n grid.
Output: The total number of different paths for the robot starting from the top-left corner and moving only down or right to eventually reach the bottom-right corner.
This problem belongs to Dynamic Programming problems.
Basic Idea (2D DP)
We can use a 2D array dp[i][j] to represent: the number of paths to reach the i-th row and j-th column.
Initialization:
- The first row and the first column are all 1, because there is only one way to go all the way right or down.
State Transition Equation:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]- Coming down from the cell above + coming over from the cell to the left.
Answer: Return
dp[m - 1][n - 1].
Space Optimization (1D DP)
Notice that dp[i][j] only depends on the value of the left cell in current row and the cell in the same column in the previous row, so the 2D array can be compressed into a 1D array.
State Transition Equation:
dp[j] = dp[j] + dp[j - 1]dp[j]represents the number of paths from above (previous row).dp[j - 1]represents the number of paths from the left (current row).
Answer: Return
dp[n - 1].
Implementation
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# Initialize dp array, size n, with all elements initially 1
# dp array represents the number of paths from the start to each column, since we can only move right in the first row,
# the initial number of paths for all columns is 1
dp = [1] * n
# Iterate through each row, start updating dp array from the second row
for i in range(1, m):
# Iterate through each column, start updating path count for each cell from the second column
for j in range(1, n):
# Update the path count for the current column, which equals the path count of the left cell (dp[j-1])
# plus the path count of the current cell (dp[j])
dp[j] += dp[j-1]
# dp[-1] represents the number of paths to the last column (bottom-right corner)
return dp[-1]
def uniquePaths2D(self, m: int, n: int) -> int:
# Initialize dp array, size m*n, all elements initially 1
# dp[i][j] represents the number of paths from the start to (i, j)
# Because in the first row and first column, the robot can only move right or down respectively, the path counts for those positions are 1
dp = [[1] * n for _ in range(m)]
# Fill the dp array according to the state transition equation to calculate the number of paths for each position
# Start updating path counts from the second row and column
for i in range(1, m):
for j in range(1, n):
# The path count for the current cell equals the path counts of the cell above it (dp[i-1][j])
# plus the cell to its left (dp[i][j-1])
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Return the number of paths reaching the bottom-right corner
return dp[m-1][n-1]
def uniquePathsBacktrack(self, m: int, n: int) -> int:
# Backtracking solution with memoization
memo = {}
def backtrack(i, j):
# If the path count for the current position is already calculated, return directly
if (i, j) in memo:
return memo[(i, j)]
# Reached the bottom-right corner, found a path
if i == m - 1 and j == n - 1:
return 1
# Reached the bottom row, can only move right
if i == m - 1:
return backtrack(i, j + 1)
# Reached the rightmost column, can only move down
if j == n - 1:
return backtrack(i + 1, j)
# Recursively calculate the path count going right and going down
memo[(i, j)] = backtrack(i, j + 1) + backtrack(i + 1, j)
return memo[(i, j)]
return backtrack(0, 0)/**
* Unique Paths - 2D DP Approach
* @param {number} m Rows
* @param {number} n Columns
* @return {number} Number of unique paths
*/
var uniquePaths2D = function(m, n) {
// Initialize m x n 2D array, filled with 1s
// Because the first row and first column only have 1 way (move all the way right or all the way down)
const dp = Array.from({ length: m }, () => Array(n).fill(1));
// Calculate starting from the 2nd row and 2nd column
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// Current cell's path count = cell above + left cell
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// Return the path count at the bottom right corner
return dp[m - 1][n - 1];
};
/**
* Unique Paths - 1D DP Optimization
* @param {number} m Rows
* @param {number} n Columns
* @return {number} Number of unique paths
*/
var uniquePaths = function(m, n) {
// Initialize 1D array, 1st row simply has 1 way
const dp = Array(n).fill(1);
// Continue downwards starting from the 2nd row
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// dp[j] originally stores the value of previous row (from above)
// dp[j-1] originally stores the value of left cell in current row (from left)
dp[j] += dp[j - 1];
}
}
// Return the path count at the bottom right corner
return dp[n - 1];
};Complexity Analysis
- Time Complexity:
O(m * n) - Space Complexity:
O(n)