【LeetCode 热题 100】62. 不同路径——（解法四）组合数学
Problem: 62. 不同路径
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(min(m, n))
- 空间复杂度：O(1)
整体思路
这段代码旨在解决 “不同路径” 问题，但它采用的是一种与动态规划完全不同的 组合数学 (Combinatorics) 方法。这种方法将问题从一个路径计数问题，抽象成了一个排列组合问题，从而可以直接通过数学公式进行计算，效率极高。
-
问题重构：
- 要从
m x n网格的左上角(0,0)移动到右下角(m-1, n-1)，机器人必须且只能向下移动m-1步，向右移动n-1步。 - 因此，无论走哪条路径，总的移动步数是固定的，即
(m-1) + (n-1) = m + n - 2步。 - 任何一条有效的路径，都可以看作是这
m + n - 2步的一个序列，其中包含了m-1个“向下”和n-1个“向右”。
- 要从
-
组合数学模型：
- 问题现在转化为：在一个总长度为
m + n - 2的序列中，选择m-1个位置放置“向下”的移动（剩下的位置自然就是“向右”），总共有多少种不同的选择方法？ - 这正是一个经典的组合问题，可以用组合数公式 C(n, k) 来表示，即“从 n 个不同元素中取出 k 个元素的组合数”。
- 在这里，
n = m + n - 2（总步数），k = m - 1（选择向下移动的步数）。 - 所以，路径的总数 =
C(m + n - 2, m - 1)。
- 问题现在转化为：在一个总长度为
-
组合数公式的计算：
- 组合数公式为:
C(n, k) = n! / (k! * (n-k)!)。 - 代入我们的变量：
C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)。 - 直接计算阶乘可能会导致非常大的中间数，从而轻易地超出
long类型的范围，导致溢出。 - 因此，代码采用了一种更聪明的迭代计算方式来求解组合数。
C(m+n-2, m-1)可以展开为：
[(m+n-2) * (m+n-3) * ... * (n)] / [(m-1) * (m-2) * ... * 1]- 代码中的循环
for (int i = 1; i <= m - 1; i++)正是实现了这个展开式。在每次迭代中：ans乘以(n - 1 + i)，这对应了分子中的一项。ans除以i，这对应了分母中的一项。
ans = ans * (n - 1 + i) / i;这种交替进行乘法和除法的方式，可以有效地保持中间结果ans尽可能小，从而避免溢出。同时，由于组合数必然是整数，这里的除法也保证是整除。
- 组合数公式为:
-
数据类型：
- 使用
long类型的ans变量是为了防止在计算过程中，即使交替乘除，中间结果也可能超出int的范围。
- 使用
完整代码
class Solution {/*** 计算从 m x n 网格的左上角到右下角的不同路径数（组合数学法）。* @param m 网格的行数* @param n 网格的列数* @return 不同的路径总数*/public int uniquePaths(int m, int n) {// ans 用于存储计算结果。使用 long 类型防止中间过程溢出。// 初始化为 1，因为 1 是乘法单位元。long ans = 1;// 该循环用于计算组合数 C(m+n-2, m-1)。// 循环 m-1 次，对应组合数公式展开后的 m-1 项。for (int i = 1; i <= m - 1; i++) {// 核心计算步骤：ans = ans * (分子项) / (分母项)// 分子项从 n 开始，递增 m-1 次，即 n, n+1, ..., n+m-2// 在循环中，当 i=1, (n-1+i) = n; 当 i=m-1, (n-1+i) = n+m-2// 分母项是 (m-1)!，即 1, 2, ..., m-1// 在循环中，i 恰好遍历了 1, 2, ..., m-1ans = ans * (n - 1 + i) / i;}// 将最终的 long 类型结果强制转换为 int 并返回。// 题目的约束保证最终结果不会超出 int 范围。return (int) ans;}
}
时空复杂度
时间复杂度：O(min(m, n))
- 循环：算法的核心是一个
for循环，它从i = 1遍历到m-1。 - 计算依据：
- 循环的执行次数是
m-1次。因此，时间复杂度为 O(m)。 - 优化说明：根据组合数的性质
C(n, k) = C(n, n-k)，我们可以选择计算C(m+n-2, m-1)或C(m+n-2, n-1)。为了使循环次数最少，我们应该选择min(m-1, n-1)作为循环的次数。因此，一个更优化的实现的时间复杂度是 O(min(m, n))。 - 尽管当前代码固定为
O(m)，但其本质是线性的，并且可以轻松优化到O(min(m, n))。
- 循环的执行次数是
空间复杂度：O(1)
- 主要存储开销：算法没有创建任何与输入规模
m或n成比例的新的数据结构。 - 辅助变量：只使用了
ans和i等几个固定数量的变量。
综合分析：
算法所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。这是解决此问题时空效率最高的方法。