Skip to main content

Unique Paths

Problem statement​

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

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

Example 2:

Input: m = 3, n = 2Output: 3Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:1. Right -> Down -> Down2. Down -> Down -> Right3. Down -> Right -> Down

Constraints:

  • 1 <= m, n <= 100

My solution​

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const dp = Array.from({
        length: n
    }, () => Array.from({
        length: m
    }, () => 0));
    
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (i === 0 || j === 0) {
                dp[i][j] = 1;
            }
        }
    }
    
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            dp[i][j] = dp[i -1][j] + dp[i][j - 1];
        }
    }
    
    return dp[n -1][m - 1]
};