题解 | #求路径#

动态规划。使用缓存的方式，因为f(m,n) = f(n,m)，所以可对 标准库的 lru_cache 装饰器进行改进，少算一半。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
from functools import lru_cache, wraps

class Solution:
    def __cache(f):
        cache = {}
      # @wraps(f)
        def wrap(_, m, n):
            computed = cache.get((m, n))
            if not computed:
                computed = f(_, m, n)
                cache[(m, n)] = computed
                cache[(n, m)] = computed
            return computed
        return wrap
    
    @__cache
#   @lru_cache
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        if m == 1 or n == 1:
            return 1
        return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)