Return the number of unique paths from top-left to bottom-right of an m x n grid moving only right or down.

Example 1:

• Input: m = 3, n = 7
• Output: 28

Constraints:

• 1 <= m, n <= 100

dp[i][j] = dp[i-1][j] + dp[i][j-1].

2D Grid Combinatorics / DP

graph TD
    Problem["Problem of Size N"] --> Sub["Break into Subproblems DP[i]"]
    Sub --> Base["Base Cases: DP[0], DP[1]"]
    Base --> Trans["State Transition: DP[i] = f(DP[i-1], DP[i-2], ...)"]
    Trans --> Table["Fill DP Table / Variables"]
    Table --> Result["Return DP[N]"]

function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      row[j] += row[j - 1];
    }
  }
  return row[n - 1];
}

• Time Complexity: O(m*n)
• Space Complexity: O(n)
• Explanation: Space-optimized 1D row DP.

function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      row[j] += row[j - 1];
    }
  }
  return row[n - 1];
}

• Time Complexity: O(m*n)
• Space Complexity: O(n)
• Explanation: Single row array cumulative summation.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

The number of ways to reach cell (i, j) is the sum of ways from above cell and left cell.

1. Base case: row 0 and col 0 are all 1.

👉 Solve this problem interactively in the DSA Lab