mediumBacktrackingPattern: Backtracking
Unique Path Finder Solution
Problem Statement
Given an `m x n` grid, where `m` is the number of rows and `n` is the number of columns, find the number of unique paths a robot can take to reach the bottom-right corner from the top-left corner. The robot can only move either down or right at any point in time.
Examples
Example 1:
Input:m = 3, n = 7
Output:28
Explanation: This example calculates the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1, n-1) in a grid, moving only right or down. The number of paths is given by the binomial coefficient C(m+n-2, m-1). For m=3, n=7, this is C(3+7-2, 3-1) = C(8, 2) = 28.
Example 2:
Input:m = 2, n = 2
Output:2
Explanation: This example calculates the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1, n-1) in a grid, moving only right or down. The number of paths is given by the binomial coefficient C(m+n-2, m-1). For m=2, n=2, this is C(2+2-2, 2-1) = C(2, 1) = 2. The paths are Right->Down and Down->Right.
Example 3:
Input:m = 1, n = 5
Output:1
Explanation: This example calculates the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1, n-1) in a grid, moving only right or down. The number of paths is given by the binomial coefficient C(m+n-2, m-1). For m=1, n=5, this is C(1+5-2, 1-1) = C(4, 0) = 1. The only path is Right, Right, Right, Right.
Constraints
- 1 <= m, n <= 100
- The grid dimensions are positive integers.
Time: O(m*n) Space: O(m*n)
This problem can be solved efficiently using dynamic programming. Create a 2D DP table `dp[m][n]` where `dp[i][j]` represents the number of unique paths to reach cell `(i, j)`. The base cases are `dp[0][j] = 1` and `dp[i][0] = 1` for all `i` and `j`. For any other cell `(i, j)`, `dp[i][j] = dp[i-1][j] + dp[i][j-1]`. The final answer is `dp[m-1][n-1]`.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def unique_paths(m: int, n: int) -> int:
dp = [[0 for _ in range(n)] for _ in range(m)]
# Initialize first column
for i in range(m):
dp[i][0] = 1
# Initialize first row
for j in range(n):
dp[0][j] = 1
# Fill the rest of 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 dp[m - 1][n - 1]