题解 | #不同路径的数目(一)# 排列数问题

题目

m行、n列的矩阵，每次只能向右一步或者向下一步， 求从左上角到右下角的路径总数

方法一：DP (时间O(mn)，空间O(mn))

1. 初始化dp数组的第一行和第一列均为1
2. 状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. 返回dp[-1][-1]即可

• Python代码：

    def uniquePaths(self , m: int, n: int) -> int:
        # DP
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

方法二：排列法 (时间O(min(m,n))，空间O(1))

• 我们要明白，不管采取什么样的走法，最终都是向下走了 m-1 步、向右走了 n-1 步，这样才能到达右下角，无非是采取的顺序问题
• 我们将向下走一步看作操作0、向右走一步看作操作1，问题就转化成求 (m-1) 个0和 (n-1) 个1的排列数问题，显然 ans = (m+n-2)!/(m-1)!(n-1)!，化简即可将较大的 (m-1)! 约分掉
• Python代码：

    def uniquePaths(self , m: int, n: int) -> int:
        # 看作是(m-1)个 0 和(n-1)个 1 的排列问题
        # ans = (m+n-2)!/(m-1)!(n-1)!
        if m < n:  m, n = n, m
        a, b = 1, 1
        for i in range(1, n):
            a *= (m-1) + i 
            b *= i 
        return a//b