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.
1int uniquePaths(int m, int n) {
2 int dp[m][n];
3 for (int i = 0; i < m; i++) {
4 dp[i][0] = 1;
5 }
6 for (int j = 0; j < n; j++) {
7 dp[0][j] = 1;
8 }
9 for (int i = 1; i < m; i++) {
10 for (int j = 1; j < n; j++) {
11 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
12 }
13 }
14 return dp[m - 1][n - 1];
15}This C implementation uses a 2D array dp to keep track of the number of ways to reach each cell. After initializing the first row and column to 1, we iteratively compute the number of ways for other cells. The final result is stored in dp[m-1][n-1], which represents the bottom-right corner.
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).
1public class Solution {
2 private long Combination(int n, int k) {
3 k = Math.Min(k, n - k);
4 long result = 1;
5 for (int i = 1; i <= k; i++, n--) {
6 result = result * n / i;
7 }
8 return result;
9 }
10
11 public int UniquePaths(int m, int n) {
12 return (int) Combination(m + n - 2, m - 1);
13 }
14}The C# code defines a Combination method to perform the core calculation of permutations in a less complex number regime.