Solutions

# Bottom up DP starting from the end, or top down DP with memoization starting from the beginning.
# dp

# Bottom-up DP - O(n*m) time, O(n*m) space
# Space optimized version: use only one array
def uniquePaths(m: int, n: int) -> int:
    dp = [[0] * n for _ in range(m)] # NB: use range to avoid creating links to the same row

    # Base cases
    dp[m-1][n-1] = 1
    for r in range(m):
        dp[r][n-1] = 1
    for c in range(n):
        dp[m-1][c] = 1

    for r in range(m-2, -1, -1):
        for c in range(n-2, -1, -1):
            dp[r][c] = dp[r+1][c] + dp[r][c+1]

    return dp[0][0]
    

# Top-down DP - O(n*m) time, O(n*m) space
# w/o memoization: O(2^(n+m)) time
def uniquePaths(m: int, n: int) -> int:
    dp = [[-1] * n for _ in range(m)]

    def dfs(r: int, c: int) -> int:
        if r >= m or c >= n:
            return 0
        if r == m-1 and c == n-1:
            return 1
        if dp[r][c] != -1:
            return dp[r][c]

        dp[r][c] = dfs(r+1, c) + dfs(r, c+1)
        return dp[r][c]

    return dfs(0,0)


# Math - O(n+m) time, O(1) space
# There are m-1 down moves and n-1 right moves, so we need to choose which m-1 of the total m+n-2 (=n-1 + m-1) moves are down (or equivalently which n-1 are right)
# So this is a combinations problem: C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)
def uniquePaths(m: int, n: int) -> int:
    from math import factorial
    return factorial(m+n-2) // (factorial(m-1) * factorial(n-1))