题解 | #求路径#

求路径

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

备注：m和n小于等于100,并保证计算结果在int范围内

数据范围：0<n,m≤100，保证计算结果在32位整型范围内 要求：空间复杂度 O(nm)，时间复杂度 O(nm) 进阶：空间复杂度 O(1)，时间复杂度 O(min(n,m))

思路：这是一道数学题，m*n的地图，从左上角到右下角需要往右走n-1步，往下走m-1步，总共需要走m+n-2步。要计算总的路径条数，就是C(m+n-2)中选(m-1)或者C(m+n-2)中选(n-1)，确定了往下或往右走的是哪几步，那么路径就确定了。所以代码非常简单。

看评论知道这道题可以用动态规划，动态规划也是可以的，最后一步要么是向下，要么向右，所以f(m*n)=f((m-1)n)+f(m(n-1))，动态规划时间、空间复杂度都会比较高，不再阐述。

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        mi = m
        if m > n:
            mi = n
        result = 1
        for i in range(mi-1):
            result = (int)((result*(m+n-2-i))/(i+1))
        return result