1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * Calculate the number of unique paths from top-left to bottom-right corner.
 * Dynamic Programming (2D) approach.
 *
 * @param {number} m - Number of rows
 * @param {number} n - Number of columns
 * @return {number} - Number of unique paths
 */
function uniquePaths(m, n) {
  // Initialize DP array
  const dp = Array(m).fill().map(() => Array(n).fill(0));
 
  // Set base cases
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1;  // First column: only one way to reach (by moving down)
  }
  for (let j = 0; j < n; j++) {
    dp[0][j] = 1;  // First row: only one way to reach (by moving right)
  }
 
  // Fill DP array
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
 
  return dp[m - 1][n - 1];
}
 
/**
 * Calculate the number of unique paths from top-left to bottom-right corner.
 * Dynamic Programming (1D) approach.
 *
 * @param {number} m - Number of rows
 * @param {number} n - Number of columns
 * @return {number} - Number of unique paths
 */
function uniquePathsOptimized(m, n) {
  // Initialize DP array for the first row
  const dp = Array(n).fill(1);
 
  // Fill DP array
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] = dp[j] + dp[j - 1];
    }
  }
 
  return dp[n - 1];
}
 
/**
 * Calculate the number of unique paths from top-left to bottom-right corner.
 * Combinatorial approach.
 *
 * @param {number} m - Number of rows
 * @param {number} n - Number of columns
 * @return {number} - Number of unique paths
 */
function uniquePathsCombinatorial(m, n) {
  // Calculate total number of moves
  const total = m + n - 2;
 
  // Choose the smaller of m-1 and n-1 as k
  const k = Math.min(m - 1, n - 1);
 
  // Calculate C(total, k)
  let result = 1;
  for (let i = 1; i <= k; i++) {
    result = result * (total - k + i) / i;
  }
 
  return Math.round(result);  // Round to handle floating-point precision issues
}
 
// Test cases
console.log(uniquePaths(3, 7));  // 28
console.log(uniquePaths(3, 2));  // 3
console.log(uniquePaths(7, 3));  // 28
console.log(uniquePaths(3, 3));  // 6
 
console.log(uniquePathsOptimized(3, 7));  // 28
console.log(uniquePathsOptimized(3, 2));  // 3
console.log(uniquePathsOptimized(7, 3));  // 28
console.log(uniquePathsOptimized(3, 3));  // 6
 
console.log(uniquePathsCombinatorial(3, 7));  // 28
console.log(uniquePathsCombinatorial(3, 2));  // 3
console.log(uniquePathsCombinatorial(7, 3));  // 28
console.log(uniquePathsCombinatorial(3, 3));  // 6