62-UniquePaths

Unique Paths

Problem can be found in here!

Solution 1: Math

def uniquePaths(m: int, n: int) -> int:
    return comb(m+n-2, n-1)

Explanation: There are m+n-2 steps to move from top-left to bottom-right. In m+n-2 steps, there are m-1 steps we have to move down and n-1 steps we have to move right. Simply put, we need to calculate how many ways we could choose m-1 down moves from m+n-2 moves, or n-1 right moves from m+n-2 moves. Therefore, the solution is .

Time Complexity: , Space Complexity: , where m is the number of rows and n is the number of columns.

Solution 2: Dynamic Programming

def uniquePaths(m: int, n: int) -> int:
    memo = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            memo[j] = memo[j - 1] + memo[j]
    return memo[-1] if m and n else 0

Time Complexity: , Space Complexity: , where m is the number of rows and n is the number of columns.