题解 | #求路径#

#我提供此题的第二种写法，动态规划前面有人讲解就不说了，用python写，真的简单太多了。

这里一定要导入math包，主要是调用math.factorial

import math

class Solution:

    def uniquePaths(self , m , n ):
  
        x = m+n-2
        
        #注意，python除法用的是 //
        
        res = math.factorial(x) // (math.factorial(m-1)*math.factorial(n-1))

        return res

思路就是,利用组合C（a,b） 意思就是从b个球中，选出a个球的总的方法数

题中，m,n代表路径的最后坐标，

那么到达这个坐标的总的步长为m+n-2(往下走了n-1步，往左走了m-1步) == b

然后从这总的步数选出n-1种(或是m-1种) == a

C(n-1, m+n-2) == !(m+n-2) / !(m-1) * !(n-1)

python有累计公式.factorial。

动态递归/递归法,开销大，很多重复。

class Solution:

    def uniquePaths(self , m , n ):
  
        if m==1 or n==1:
        	return 1
        else:
        	return Solution.uniquePaths(m-1,n) + Solution.uniquePaths(m.n-1)