Skip to content

62. Unique Paths

https://leetcode.com/problems/unique-paths/

js
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  function factorial(x) {
    if (x === 0 || x === 1) {
      return 1
    }
    return x * factorial(x - 1)
  }

  return factorial(m + n - 2) / factorial(m - 1) / factorial(n - 1)
}
js
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let 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] + dp[j]
        }
    }
    return dp[n - 1]
};
py
class Solution(object):

    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        factorial = lambda x: 1 if x == 0 or x == 1 else x * factorial(x - 1)
        return factorial(m + n - 2) / factorial(m - 1) / factorial(n - 1)
py
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                dp[j] = dp[j - 1] + dp[j]
        return dp[n - 1]