Medium

Unique Paths

054

Return the number of ways to move from the top-left to bottom-right of an m by n grid moving only right or down.

EXAMPLES

Example 1

Input
{
  "m": 3,
  "n": 7
}

Output
28

FUNCTION SHAPE

m: intn: int→int

SOLUTION NOTE

Classic grid DP. Each cell's count = sum of paths from right and down neighbors.

Reveal reference solution +

pythonREFERENCE

def uniquePaths(self, m: int, n: int) -> int:
    @cache
    def dp(i, j):
        if i == m - 1 and j == n - 1:
            return 1
        if i >= m or j >= n:
            return 0
        return dp(i + 1, j) + dp(i, j + 1)

    return dp(0, 0)

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗