The key idea in this approach is to use a 2D table to store the number of ways to reach each cell. Initialize the first row and first column by 1 because there is only one way to reach any cell in the first row (all rights) and the first column (all downs). For the rest of the cells, the number of ways to reach that cell is the sum of the number of ways to reach the cell directly above it and the cell directly to the left of it.
Time Complexity: O(m * n) because each cell is computed once. Space Complexity: O(m * n) for the 2D DP array.
1def uniquePaths(m, n):
2 dp = [[1] * n for _ in range(m)]
3 for i in range(1, m):
4 for j in range(1, n):
5 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
6 return dp[m-1][n-1]Python uses list comprehension to initialize the 2D list dp. Looping over the list fills in the number of unique paths for all cells, with the solution found at dp[m-1][n-1].
A different method is to use combinatorics. The robot makes a total of (m + n - 2) moves, consisting of (m - 1) downward moves and (n - 1) rightward moves. The number of unique paths to organize these actions is the number of combinations of downs and rights: Combination(m+n-2, m-1) or Combination(m+n-2, n-1). This approach avoids the need for additional memory allocation for simple calculations.
Time Complexity: O(min(m, n)) for optimal comb calculations. Space Complexity: O(1).
1#include <algorithm>
2
3long long combination(int n, int k) {
4 k = std::min(k, n - k);
5 long long result = 1;
6 for(int i = 1; i <= k; i++, n--) {
7 result = result * n / i;
8 }
9 return result;
10}
11
12int uniquePaths(int m, int n) {
13 return (int)combination(m + n - 2, m - 1);
14}The C++ solution finds the combination of moves by optimally computing the value, minimizing integer range overflow while maintaining efficiency.