不同路径

标签: 数学 动态规划 组合数学

难度: Medium

一个机器人位于一个 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

Submission

运行时间: 44 ms

内存: 15.3 MB

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        memo = dict()

        def dp(i, j):
            if i < 0:
                return 0
            if j < 0:
                return 0
            if i == 0 and j == 0:
                return 1 

            if (i, j) in memo:
                return memo[(i, j)]
            
            res = dp(i-1, j) + dp(i, j-1)
            memo[(i, j)] = res
            return res
        
        return dp(m-1, n-1)

Explain

这个题解使用动态规划的思路来解决问题。定义函数 dp(i, j) 表示从起点走到位置 (i, j) 的不同路径数量。机器人每次只能向下或向右移动,因此到达 (i, j) 的路径数等于到达 (i-1, j) 和 (i, j-1) 的路径数之和。使用记忆化搜索避免重复计算子问题,将已计算过的结果存储在 memo 字典中。边界条件是当 i 或 j 小于0时路径数为0,当到达起点 (0, 0) 时路径数为1。最终返回 dp(m-1, n-1) 即为从起点到终点的不同路径总数。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        memo = dict()

        def dp(i, j):
            # 当 i 或 j 小于0时,返回0,表示无法到达
            if i < 0:
                return 0
            if j < 0:
                return 0
            # 当到达起点 (0, 0) 时,返回1,表示找到一条路径
            if i == 0 and j == 0:
                return 1 

            # 如果 (i, j) 的结果已经计算过,直接返回记忆化的值
            if (i, j) in memo:
                return memo[(i, j)]
            
            # 到达 (i, j) 的路径数等于到达 (i-1, j) 和 (i, j-1) 的路径数之和
            res = dp(i-1, j) + dp(i, j-1)
            # 将计算结果存入 memo 字典中
            memo[(i, j)] = res
            return res
        
        # 返回从起点到终点的不同路径总数
        return dp(m-1, n-1)

Explore

在递归函数中,当(i, j)位置超出网格边界时返回0的原因是,这代表机器人不能进入这些位置,因此这些位置不存在有效的路径到达它们。此设定并不意味着机器人不能往回走,而是根据题目设定,机器人只能向右或向下移动,不允许向左或向上,因此超出边界的位置自然不在考虑范围内。

当机器人到达起点(0, 0)时,路径数为1是因为起点是路径的开始点,且只存在一种方式在起点上开始路径——即站在起点上。这是由题目定义决定的,因为所有的路径都从此点出发。在这个问题的设定中,不存在其他情况使得起点路径数不为1,因为起点总是固定的,且机器人总是从这一点开始移动。

对于非常大的网格尺寸,我们可以考虑以下几种优化策略:1. 使用迭代而非递归方法,通过迭代计算动态规划表,避免递归的深度限制和栈溢出的问题。2. 采用空间优化技术,例如只存储动态规划表中的当前行和前一行,因为计算当前行值只需要前一行的数据。这可以将空间复杂度从O(m*n)降低到O(min(m,n))。3. 如果问题允许,还可以使用并行处理技术,利用多线程或分布式计算来加速整个计算过程。