Unique Paths

The problem description can be found in LeetCode.

Approach

The robot can move either down or right, which means that we have a kind of decision tree: at every step we can take one of the two directions.

Let's derive a partial space tree by first going down and then right:

Where we marked the following:

• Red: invalid coordinates.
• Blue: the repeated work for the coordinate (2, 1).
• Green: a valid solution.

Since we have some repeated work, we can use memoization to store some already calculated results.

Solution

from typing import Dict, Tuple


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        def dfs(row: int, col: int, memo: Dict[Tuple[int, int], int]):
            if (row, col) in memo:
                return memo[(row, col)]
            if row == m - 1 and col == n - 1:
                return 1
            if not (0 <= row < m) or not (0 <= col < n):
                return 0

            ans = 0
            ans += dfs(row + 1, col, memo)
            ans += dfs(row, col + 1, memo)

            memo[(row, col)] = ans

            return ans

        return dfs(0, 0, {})

Complexity

• Time: $O(mn)$
• Space: $O(mn)$

Where $m$ and $n$ are the two inputs of the function.