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.
1class Solution {
2 public int uniquePaths(int m, int n) {
3 int[][] dp = new int[m][n];
4 for (int i = 0; i < m; i++) {
5 dp[i][0] = 1;
6 }
7 for (int j = 0; j < n; j++) {
8 dp[0][j] = 1;
9 }
10 for (int i = 1; i < m; i++) {
11 for (int j = 1; j < n; j++) {
12 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
13 }
14 }
15 return dp[m - 1][n - 1];
16 }
17}Java implementation uses a 2D array to store the number of ways to reach each cell. The process is similar to other languages, filling the results based on the number of ways from above and left cells.
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 <stdio.h>
2
3long long combination(int n, int r) {
4 if(r > n / 2) r = n - r;
5 long long ans = 1;
6 for(int i = 1; i <= r; i++, n--) {
7 ans = ans * n / i;
8 }
9 return ans;
10}
11
12int uniquePaths(int m, int n) {
13 return (int)combination(m + n - 2, m - 1);
14}This C code calculates the combinatorial value of picking (m-1) from (m+n-2) using an iterative approach to avoid overflow issues compared to factorial division directly.