62. 不同路径

题目

• 题号：62
• 难度：中等
• https://leetcode-cn.com/problems/unique-paths/

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例1

输入：m = 3, n = 7
输出：28

实现

思路1 动态规划

该题还是很容易找到动态转移方程的。可以有以下两种构建方法：

1. 若定义f(i,j)为从网格左上角走到坐标(i, j)的路径数量，从题目我们知道想走到(i, j)只可能从(i-1, j)往右走一步到达或者从(i, j-1)往下走一步到达，那么动态转移方程可以写为：。此时我们应该把网格右下角的坐标代入方程递归求解。
2. 若定义f(i,j)为从坐标(i, j)走到网格右下角的路径数量，从题目我们知道从(i, j)开始只有向右和向下两种走法，因此动态转移方程可以写为：。此时我们应该把网格左下角的坐标代入方程递归求解。

以上两种方法都能求解，不过都需要注意边界问题。
对于第一种方法，由于第一行和第一列都处在边界，所以初始化为1.
对于第二种方法，是最后一行和最后一列处在边界，所以初始化为1.
这里以第一种方法的代码为例：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 维护一个dp matrix，第一行和第一列为0
        dp = [[1]*n] + [[1] + [0] * (n-1) for _ in range(m-1)]
        for x in range(1, m):
            for y in range(1, n):
                dp[x][y] = dp[x-1][y] + dp[x][y-1]
        return dp[-1][-1]

时间复杂度：
空间复杂度：
**

思路2 优化思路1

思路1的代码新开辟了一个m*n的dp数组，而实际上这个空间开销可以缩小到只使用一个长度为n的dp数组。

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

此时动态转移方程为：dp[j] = dp[j]+dp[j-1]。这里等式右边的dp[j]表示的是位置(i-1, j)（来自上一轮更新）dp[j-1]表示的是位置(i, j-1)。
空间复杂度：
**

思路3 排列组合

通过数学中的组合知识可以快速求得答案。
对mn的网格，从左上角到右上角的移动次数其实固定为m+n-2次，且其中m-1次往下，n-1次往右。因此求路径的总数，就是看这总共m+n-2次的移动过程中选择*m-1次向下移动的方案数，即

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)