Unique Paths
A robot is located at the top-left corner of an m x n grid (marked as (0, 0)).
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 as (m - 1, n - 1)).
Your task is to determine how many unique paths the robot can take to reach the destination.
Example
Input: m = 3, n = 3 Output: 6 S → □ → □ ↓ ↓ ↓ □ → □ → □ ↓ ↓ ↓ □ → □ → E
Explanation: Starting from the top-left corner S, you can move only right or down to reach the bottom-right corner E. There are 6 unique paths you can take:
Right → Right → Down → Down
Right → Down → Right → Down
Right → Down → Down → Right
Down → Right → Right → Down
Down → Right → Down → Right
Down → Down → Right → Right
We will be using Dynamic Programming to solve the Unique Paths problem efficiently.
To reach a cell (i, j) in the grid, you can come either:
From the cell above (i - 1, j) (i.e., moved down), or
From the cell to the left (i, j - 1) (i.e., moved right).
So, the total number of unique paths to reach cell (i, j) is the sum of unique paths to reach the cell above it and the cell to the left of it:
Recursive Relation: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
Algorithm
- Initialize a 2D DP table dp of size m x n, where each cell initially stores 1.
The first row and first column are all set to 1 because there's only one way to reach those cells — by moving straight right or straight down respectively.
- Fill the rest of the table using the recurrence:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- The value at
dp[m - 1][n - 1]will hold the total number of unique paths.
def unique_paths(m: int, n: int) -> int:
d = [[1] * n for _ in range(m)]
for col in range(1, m):
for row in range(1, n):
d[col][row] = d[col - 1][row] + d[col][row - 1]
return d[m - 1][n - 1]Time Complexity: O(m * n) As we compute values for all m * n cells once.
Space Complexity: O(m * n) As we store results in a 2D DP table.