矩阵中唯一路径的数量

Question

我遇到的问题是：

机器人位于m x n网格的左上角。机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角。有多少条可能的唯一路径？

我提交的代码是：

class Solution(object):
def uniquePaths(self,m,n):
# m : (int) rows
# n : (int) cols
mat = [[0] * n] * m
for i in range(n):
mat[0][i] = 1

for i in range(m):
mat[i][0] = 1
for i in range(1,m):
for j in range(1,n):
mat[i][j] = mat[i - 1][j] + mat[i][j - 1]
return mat[m - 1][n - 1]

提交后，我才知道我的代码只比 21% 的其他提交快。这意味着我的代码不是最佳的。所以出于好奇，我检查了另一个比我快得多的提交。

更好的解决方案是：

class Solution(object):
def uniquePaths(self, m, n):
p = 1
for i in xrange(n,m+n-1):
p *= i
return p/self.factorial(m-1)
def factorial(self,n):
if n == 0:
return 1
return n*self.factorial(n-1)

如您所见，它的时间复杂度是线性的，而我的时间复杂度是二次的。但我无法理解它背后的逻辑。

Answer 1

你不需要计算机程序。这是一个简单的组合数学问题。想象一下 m 个向右箭头和 n 个向下箭头。问这个问题的另一种方法是我们可以用多少种方式排列这些箭头？我们可以从 m+n 中选择 m 个点作为向右箭头。所以答案是二项式(m， m + n(