62. Unique Paths

Solution 1: DFS (TLE)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        def dfs(rowIdx, colIdx):
            # Out of bound
            if rowIdx >= m or colIdx >= n:
                return 0
            # Reach the endpoint
            if rowIdx == m - 1 and colIdx == n - 1:
                return 1
            
            pathMoveDown = dfs(rowIdx + 1, colIdx)
            pathMoveRght = dfs(rowIdx, colIdx + 1)
            return pathMoveDown + pathMoveRght
            
        ans = dfs(0, 0)
        return ans

Time Complexity: O(2^(M+N))
Space Complexity: O(M+N) // (M+N) Times recursive call

Solution 2: Top-down DP (DFS + Memoization)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [n*[0] for row in range(m)]
        def dfs(idxRow, idxCol):
            # Out of bound
            if idxRow >= m or idxCol >= n:
                return 0
            # Use cached result
            if dp[idxRow][idxCol]:
                return dp[idxRow][idxCol]
            # Reach target
            if idxRow == m - 1 and idxCol == n - 1:
                return 1
            
            pathDown = dfs(idxRow + 1, idxCol)
            pathRght = dfs(idxRow, idxCol + 1)
            dp[idxRow][idxCol] = pathDown + pathRght
            return dp[idxRow][idxCol]
        
        ans = dfs(0, 0)
        return ans

Time Complexity: O(MN) // The unique path from each of cell to endpoint is calculated only once and memoized
Space Complexity: O(MN)

Solution 3: Bottom-up DP

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

Solution 4: Math (Combination)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        ans = 1
        # C(m + n - 2), (m - 1)
        i = m + n - 2
        j = 1
        while i > max(m - 1, n - 1):
            ans = ans * i // j
            i -= 1
            j += 1
        return ans

Time Complexity: O(M+N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/unique-paths/discuss/22958/Math-solution-O(1)-space
https://leetcode.com/problems/unique-paths/discuss/1581998/C%2B%2BPython-5-Simple-Solutions-w-Explanation-or-Optimization-from-Brute-Force-to-DP-to-Math