刷题记录动态规划-6: 62. 不同路径

题目：62. 不同路径

难度：中等

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

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

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

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

示例 4：

输入：m = 3, n = 3
输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

一、模式识别

本题我一共找到了三种解法：

首先最容易想到的就是基于递归的DFS（深度优先搜索），

然后如果沿着递推公式能想到从终点返回起点这一层就能写出动态规划解法

最后代码随想录还给出了算组合数的方法（数论），我数学没那么好，想不到

1.DFS

该方法顺着题干很容易想到，而且该方法就是动态规划方法的递推公式

2.动态规划

本题属于经典动态规划问题，而且动规的很多要素题干中已经直接给出

五部曲：

1.动规数组意义：位于位置(i, j)时剩余的总步数

2.递推公式：dp(i, j) = dp(i - 1, j) + dp(i, j - 1)

解释：

机器人处于位置(i, j)时，每次只能向下或者向右移动一步两种选择，

分别可以到达(i - 1, j)和位置(i, j - 1)，

3.初始化：题干：一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）

4.遍历顺序：本题常规，根据递推公式：

行遍历套列遍历或列遍历套行遍历均可，但注意是从终点反向到起点

5.举例：当机器人走到边缘位置(m == 1 or n == 1)，路径便只剩下一条

3.数论：算组合数

无论怎么走，从起点(m, n)到终点(1, 1)都要走m + n - 2步，

其中，横向m - 1步，纵向n - 1步

因此该问题就顺理成章的转化成了C(m + n - 2), (m - 1)的组合问题

二、代码实现

1.DFS

这方法很好想，而且代码简介可读性强，但就是有个小小的问题：会超时！

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

问题源于其指数级的时间复杂度：O(2^(m + n - 1) - 1)

2.动态规划

（1）二维OMN空间写法

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

时间复杂度：O(m × n)
空间复杂度：O(m × n)

耗时：0ms

（2）一维ON空间写法

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

时间复杂度：O(m × n)
空间复杂度：O(n)

耗时：3ms

可读性有点差，所以稍微解释一下，和二维空间代码的对应关系：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 和 dp[j] += dp[j - 1]

dp[i][j]: 更新后的dp[j]

dp[i - 1][j]: 更新前的dp[j]

dp[i][j - 1]: dp[j - 1]

3.数论：算组合数

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        num = 1
        a, b = m + n - 2, min(m - 1, n - 1)
        count = b
        while count > 0:
            num *= a
            a -= 1
            while b > 0 and num % b == 0:
                num //= b
                b -= 1
            count -= 1
        return num