62. Unique Paths (opens new window)

Description

Difficulty: Medium

Related Topics: Math (opens new window), Dynamic Programming (opens new window), Combinatorics (opens new window)

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 * 10⁹.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= m, n <= 100

Solution

Language: JavaScript

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 * 思路：
 * 每一格的路径由其上一格和左一格决定。
 * 方法：动态规划
 * 动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
 * 注意：对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为1
 * 建立m*n的矩阵，注意第0行和第0列元素均为1
 * 按列依次遍历矩阵，当前格的路径数量由其左边和上面格的路径数量决定
 * 返回最后一个格的路径数量
 * 优化
 * 只用长度为n的列表记录路径
 * 使用一个长度为n的列表记录路径
 * 将自身与上一格的路径相加得到右一格
 * 
 * 方法二：组合数学
 * 思路与算法
 * 从左上角到右下角的过程中，我们需要移动 m+n-2m+n−2 次，其中有 m-1m−1 次向下移动，n-1n−1 次向右移动。因此路径的总数，就等于从 m+n-2m+n−2 次移动中选择 m-1m−1 次向下移动的方案数，即组合数：

 */
var uniquePaths = function(m, n) {
    let [x, y, ans] = [n, 1, 1];
    
    while (y < m) {
        ans = Math.floor(ans * x / y)
        y++;
        x++;
    }
    
    return ans;
};