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.
1#include <vector>
2using namespace std;
3
4int uniquePaths(int m, int n) {
5 vector<vector<int>> dp(m, vector<int>(n, 1));
6 for (int i = 1; i < m; i++) {
7 for (int j = 1; j < n; j++) {
8 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
9 }
10 }
11 return dp[m - 1][n - 1];
12}The C++ solution uses a vector of vectors to form a 2D DP table. The initialization and iteration are straightforward, resulting in storing the answer in 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).
1import math
2
3def uniquePaths(m, n):
4 return math.comb(m + n - 2, m - 1)Pythons's math library directly provides the comb function for comfortable calculation through native functionality.