[LeetCode] 62. Unique Paths

Problem : https://leetcode.com/problems/unique-paths/

The last step to reach one cell is either from the cell on top or cell on left.

Let paths(i, j) is the unique paths to reach cell (i, j).

paths(i, j) = paths(i-1, j)+ paths(i, j -1).

i is row index which's value range is 1 to M

j is column index which's value range is 1 to N

Use "functools.lru_cache" to cache the intermediate result of the top-down approach.

Time Complexity = O ( M * N ) as the code needs to visit each cell once.

Space Complexity = O ( M * N ) for the memorization cache.

from functools import lru_cache

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        
        @lru_cache(maxsize=None)
        def paths(i, j):
            if j <= 0 or i <= 0:
                return 0
            
            # 1 step to start from the top-left cell
            if i == 1 and j == 1:
                return 1
            
            return paths(i, j-1) + paths(i-1, j)
        
        return paths(m, n)