62. Unique Paths (Math, Dynamic Programming, Combinatorics)

링크 - https://leetcode.com/problems/unique-paths/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) DP

우리는 dp를 통해 이 문제를 풀 수 있다. dp[i][j]에 갈 수 있는 unique path의 개수는 dp[i-1][j] 와 dp[i][j-1]를 더한것과 같다.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]

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

        return dp[-1][-1]

Time Complexity: O(N * M)

Space Complexity: O(N * M)

2) Math

이 문제를 푸는 수학 공식이 있으므로 space complexity를 O(1)로 할 수 있다.

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

Time Complexity: O((M+N)(log(M+N)loglog(M+N))^2)

Space Complexity: O(1)