🌵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]