[Leetcode] 62. Unique Paths

문제 바로가기

Combination

Time Complexity: O(min(m, n))
Space Complexity: O(1)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # combination: pick min(m-1, n-1) steps from total steps\
        total = m + n - 2
        smaller = min(m, n) - 1
        denominator, numerator = 1, 1  # 분모, 분자
        
        for i in range(smaller):
            denominator *= total - i
            numerator *= i + 1
        
        return denominator // numerator

Dynamic Programming

Bottom up

Time Complexity: O(mn)
Space Complexity: O(mn)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        memo = [[0 for _ in range(n)] for _ in range(m)]
        for r in range(m):
            memo[r][0] = 1
        for c in range(n):
            memo[0][c] = 1
        
        for r in range(1, m):
            for c in range(1, n):
                memo[r][c] = memo[r-1][c] + memo[r][c-1]
        
        return memo[-1][-1]

Top down

Time Complexity: O(mn)
Space Complexity: O(mn)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        memo = [[0 for _ in range(n)] for _ in range(m)]
        for r in range(m):
            memo[r][0] = 1
        for c in range(n):
            memo[0][c] = 1
        
        def findPaths(m: int, n: int) -> int:
            if not memo[m][n]:
                memo[m][n] = findPaths(m-1, n) + findPaths(m, n-1)
            return memo[m][n]
        
        return findPaths(m-1, n-1)