[leetcode] 62. Unique Paths

문제 : https://leetcode.com/problems/unique-paths/description/

난이도 : Medium

 

풀이

1) dp로 풀기

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if not m or not n:
            return 0

        cur = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                cur[j] += cur[j - 1]
        
        return cur[-1]

 

2) 수학적으로 풀기

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return factorial(m+n-2) // factorial(m-1) // factorial(n-1)