62. Unique Paths

class Solution:
#     # recursive solution - times out
#     def uniquePaths(self, m: int, n: int) -> int:
#         if (m == 1) or (n == 1):
#             return 1
        
#         # first step right
#         right_step = self.uniquePaths(m - 1, n)
#         # first step down
#         down_step = self.uniquePaths(m, n - 1)
        
#         return right_step + down_step

#     # dynamic programming
#     def uniquePaths(self, m: int, n: int) -> int:
#         solutions = [[1] * m] * n
        
#         for i in range(1, n):
#             for j in range(1, m):
#                 solutions[i][j] = solutions[i - 1][j] + solutions[i][j - 1]
        
#         return solutions[n - 1][m - 1]

    # recursion with memoization
    cache = {}
    def uniquePaths(self, m: int, n: int) -> int:
        if (m, n) in self.cache:
            return self.cache[m, n]
        if (m < 1) or (n < 1):
            return 0
        elif (m == 1) and (n == 1):
            return 1
        else:
            self.cache[m, n] = self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)
            return self.cache[m, n]