Leetcode 剑指 Offer II 098.不同路径

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

一个机器人位于一个 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 * 10^9

题目思考

如何优化时间和空间复杂度?

解决方案

方法 1

分析题目, 机器人只能向下或向右移动, 我们可以利用这一点, 累加当前坐标的左边和上边相邻坐标的路径数来得到当前坐标的路径数
显然这就是动态规划的思路:
- 设 dp[r][c] 代表坐标(r,c)的路径数
- 初始化 dp[0][0] = 1, 其他值全是 0, 表示开始时起点的路径数为 1
- 然后进行状态转移: dp[r][c] = dp[r-1][c] + dp[r][c-1] (如果 r 或 c 为 0, 则相应的 r-1 或 c-1 的 dp 值就是 0, 只能从另一个方向转移而来)
- 最终右下角坐标的 dp[m-1][n-1] 就代表总路径数
下面的代码有详细的注释, 方便大家理解

复杂度

时间复杂度 O(MN): 需要两重循环求 DP 值
空间复杂度 O(MN): 二维 DP 数组的空间消耗

代码

class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[0] * n for _ in range(m)]for r in range(m):for c in range(n):if (r, c) == (0, 0):# 起点dp值初始化为1dp[r][c] = 1else:# 左侧邻居路径数, 不存在时为0ldp = 0 if c == 0 else dp[r][c - 1]# 上侧邻居路径数, 不存在时为0udp = 0 if r == 0 else dp[r - 1][c]# 累加两个邻居的路径数dp[r][c] = ldp + udp# 最终结果就是右下角路径数return dp[m - 1][n - 1]

方法 2

上面的 DP 做法固然可以解决这个问题, 那是否可以继续优化呢?
答案是肯定的, 我们从另一个角度来思考这个问题, 机器人一共移动 m+n-2 次, 然后每次移动要么向下, 要么向右, 一共向下移动 m-1 次, 向右移动 n-1 次
相当于从总移动次数 m+n-2 中选取 m-1 个, 我们可以利用数学求组合数的方法, 也即 C(m+n-2, m-1), 得到的值就是对应的总路径数
这里可以额外进行一些优化, 使用 m 和 n 中的较小值来计算组合数, 对应的时间复杂度也是两者的较小值
下面的代码有详细的注释, 方便大家理解

复杂度

时间复杂度 O(min(M,N)): 求组合数时需要累乘 M-1 或 N-1 次, 取两者较小值
空间复杂度 O(1): 没有使用额外变量

代码

class Solution:def uniquePaths(self, m: int, n: int) -> int:# 共有m+n-2次移动, 然后从中选择m-1次向下, 剩下n-1次向右# 所以总路径数就是组合数C(m+n-2,m-1) (也等于C(m+n-2,n-1))# 额外优化, 使用m和n的较小值来计算组合数mn = min(m, n)return math.comb(m + n - 2, mn - 1)