Overview

A robot is located at the top-left corner of an m × n grid. It can only move right or down at each step. Count the number of unique paths from the top-left to the bottom-right corner.

Implement uniquePaths(m, n).

Constraints

• 1 ≤ m, n ≤ 100.
• The answer fits in a 32-bit integer.
• Aim for $O(m \times n)$ time with $O(n)$ space using a rolling array.

Examples

uniquePaths(3, 7);  // 28
uniquePaths(3, 2);  // 3
uniquePaths(1, 1);  // 1
uniquePaths(2, 2);  // 2

Notes

• DP approach: dp[i][j] = dp[i-1][j] + dp[i][j-1]. The first row and first column are all 1 (only one way to reach any cell on the edge).
• Space optimization: you only need the previous row, so a 1D array of size n suffices.
• Math approach: the answer is the binomial coefficient $\binom$ — choosing which m-1 of m+n-2 steps are "down".

Solution

function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j - 1];
    }
  }

  return dp[n - 1];
}

Resources

• Unique Paths — LeetCode
• Dynamic Programming — Wikipedia