class Solution:
    def __init__(self):
        self.memo = {}
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m == 1 or n == 1:
            return 1

        if m < n:
            small, big = m, n
        else:
            small, big = n, m

        key = "{}:{}".format(small, big)

        if not key in self.memo:
            self.memo[key] = self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)


        return self.memo[key]