求路径

问题简述

一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

求路径_牛客题霸_牛客网

思路：动态规矩

Python：递归

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == m and j == n:
                return 1
            if i > m or j > n: return 0
            
            return dp(i + 1, j) + dp(i, j + 1)
        
        return dp(1, 1)