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.
1var uniquePaths = function(m, n) {
2 let dp = Array(m).fill().map(() => Array(n).fill(1));
3 for(let i = 1; i < m; i++) {
4 for(let j = 1; j < n; j++) {
5 dp[i][j] = dp[i-1][j] + dp[i][j-1];
6 }
7 }
8 return dp[m-1][n-1];
9};JavaScript uses nested arrays to simulate the 2D table dp. After initializing base cases, it fills the table to compute each cell's path count, concluding in the bottom-right corner value.
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.