Unique Paths 是 LeetCode Hot 100 里面一道非常经典的动态规划题。
不过这道题很有意思，因为它虽然通常会被归类到动态规划里，但实际上还有一种非常漂亮、而且更简洁的做法：
组合数学
你给出的这份 Java 代码，用的就不是传统的二维 dp
这种写法非常巧妙，因为它抓住了这道题最本质的地方：
路径的不同，本质上只是若干步“向右”和若干步“向下”的排列方式不同。
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定两个整数 m 和 n，表示一个机器人位于一个 m x n 的网格左上角。
机器人每次只能向下或者向右移动一步。 现在要求它从左上角出发，走到右下角，一共有多少种不同的路径。
例如一个 3 x 7 的网格：
-
起点在左上角
-
终点在右下角
-
机器人只能：
-
向右走
-
向下走
-
题目要我们求的是：
总共有多少种不同的走法。
注意这里不是求最短路径，因为无论怎么走，只要从左上到右下，步数其实都一样； 题目真正问的是：
这些固定步数的走法一共有多少种排列方式。
示例
示例 1
输入：m = 3, n = 7
输出：28
意思是一个 3 行 7 列的网格，从左上角走到右下角，一共有 28 种不同路径。
示例 2
输入：m = 3, n = 2
输出：3
因为从左上角到右下角，总共需要走：
-
向下
m - 1 = 2次 -
向右
n - 1 = 1次
也就是总共 3 步，其中 2 步向下、1 步向右。
所有可能的走法有：
下 下 右
下 右 下
右 下 下
所以答案是 3。
最容易想到的思路：动态规划
这道题大多数人第一次接触时，第一反应通常是动态规划。
因为对于网格中的某个位置 (i, j) 来说，它只能从两个地方走过来：
-
上面
(i - 1, j) -
左边
(i, j - 1)
所以到达当前位置的路径数就是：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
这就是标准的动态规划状态转移。
例如：
-
第一行的所有位置，路径数都只能是 1
-
第一列的所有位置，路径数也只能是 1
-
其他位置由上方和左方相加得到
这个思路完全正确，也是这道题最经典的基础解法。
但是你给出的代码并没有走这条路，而是用了一个更简洁的数学方法。
核心思路：把问题转成组合数
这道题最本质的地方在于：
从左上角走到右下角，不管怎么走，总步数其实是固定的。
假设网格大小是 m x n：
-
总共需要向下走：
m - 1
步
-
总共需要向右走：
n - 1
步
所以总步数就是：
(m - 1) + (n - 1) = m + n - 2
而一条路径，本质上就是在这 m + n - 2 步里，选择哪些位置走“向下”，其余位置自然就是“向右”。
所以问题就变成了：
从总共 m + n - 2 步中，选出 m - 1 步作为向下，有多少种选法？
这其实就是一个组合数问题：
C(m + n - 2, m - 1)
当然你也可以写成：
C(m + n - 2, n - 1)
两者是等价的。
这就是这道题最漂亮的数学转化。
你的代码在做什么？
你给出的代码如下：
class Solution {
public int uniquePaths(int m, int n) {
long ans = 1;
for (long up = n, down = 1; down < m; down++, up++)
ans = ans * up / down;
return (int) ans;
}
}
这段代码本质上就是在计算：
C(m + n - 2, m - 1)
只不过没有直接调用阶乘，而是通过逐步乘除的方式来避免中间数过大。
这也是实现组合数时非常常见的一种技巧。
Java 代码（带注释）
下面我把这段代码加上注释重新整理一下：
class Solution {
public int uniquePaths(int m, int n) {
long ans = 1;
// 计算组合数 C(m+n-2, m-1)
// 这里采用乘一项、除一项的写法，避免直接算阶乘带来的溢出风险
for (long up = n, down = 1; down < m; down++, up++) {
ans = ans * up / down;
}
return (int) ans;
}
}
代码拆解
这段代码不长，但如果第一次接触组合数写法，可能会有点疑惑。 下面一步一步来看。
1. 为什么总步数是 m + n - 2？
从左上角走到右下角：
-
行数从第 1 行走到第
m行，需要向下走m - 1次 -
列数从第 1 列走到第
n列，需要向右走n - 1次
所以总步数固定为：
(m - 1) + (n - 1) = m + n - 2
这一点非常关键，因为它说明：
所有路径的长度都是一样的，区别只在于这些步子的顺序。
2. 为什么可以转化成组合数？
假设我们把一条路径写成一个序列：
-
D表示向下 -
R表示向右
例如对于 m = 3, n = 7：
-
向下需要
2步 -
向右需要
6步
那么任何一条合法路径都可以写成长度为 8 的序列，其中：
-
有
2个D -
有
6个R
例如：
D D R R R R R R
D R D R R R R R
R R D R D R R R
等等。
所以问题本质上就是：
在 8 个位置中挑 2 个位置放 D，其余放 R。
这就是组合数：
C(8, 2)
推广到一般情况，就是：
C(m + n - 2, m - 1)
3. 为什么代码里 up 从 n 开始？
for (long up = n, down = 1; down < m; down++, up++)
我们来对应一下组合数公式。
组合数：
C(m+n-2, m-1)
可以展开成：
(m+n-2)! / ((m-1)! * (n-1)!)
进一步可以写成连乘形式：
[(n) * (n+1) * (n+2) * ... * (m+n-2)] / [1 * 2 * 3 * ... * (m-1)]
也就是说：
-
分子从
n开始，一直乘到m + n - 2 -
分母从
1开始，一直乘到m - 1
这正好对应代码里的：
-
up = n -
down = 1
然后每轮同时递增。
所以这段循环其实就是在一项一项地计算组合数。
4. 为什么 down < m？
for (long up = n, down = 1; down < m; down++, up++)
因为我们要乘除的分母部分是：
1, 2, 3, ..., m-1
所以 down 应该从 1 一直走到 m - 1。
而循环条件写成：
down < m
恰好就表示 down 最大取到 m - 1。
5. 为什么每次都可以直接 ans = ans * up / down？
ans = ans * up / down;
这一步很多人第一次看会担心：
这样先乘再除，会不会出现不能整除的问题？
从数学上讲，最终结果一定是组合数，是整数。 而这种逐步乘除的方式在这里是成立的，因为整个过程本质上是在按组合数的连乘形式计算，最终每一步都能保证中间结果仍然是正确值。
此外，这里用的是 long，也是为了让中间计算更安全。
这种写法相比直接算三个阶乘再相除，有两个优点：
-
不需要真的去算很大的阶乘
-
中间数增长更可控，不容易溢出
所以这是组合数计算中一个非常常见的技巧。
6. 为什么最后转成 int 返回？
return (int) ans;
因为题目给定的数据范围保证最终答案在 int 范围内。
不过中间计算过程为了更安全，仍然使用了 long：
long ans = 1;
这是一个很稳妥的写法。
手动模拟一遍
我们用一个简单例子来走一遍：
m = 3, n = 7
那么：
-
向下走
m - 1 = 2次 -
向右走
n - 1 = 6次 -
总步数
= 8
答案应该是：
C(8, 2) = 28
现在来看代码怎么计算。
初始：
ans = 1
up = 7
down = 1
第一次循环
ans = 1 * 7 / 1 = 7
然后：
-
up = 8 -
down = 2
第二次循环
ans = 7 * 8 / 2 = 28
然后：
-
down = 3
此时不满足 down < m（因为 m = 3），循环结束。
最终返回：
28
这正好就是答案。
再看一个小例子
例如：
m = 3, n = 2
总步数：
3 + 2 - 2 = 3
向下走：
m - 1 = 2
所以答案是：
C(3, 2) = 3
代码里：
-
up = 2 -
down = 1
第一次
ans = 1 * 2 / 1 = 2
第二次
ans = 2 * 3 / 2 = 3
最终答案也是 3。
为什么这种方法是正确的？
因为这道题里每条路径都可以一一对应成一个由：
-
m - 1个“向下” -
n - 1个“向右”
组成的序列。
而不同路径的区别，只在于这些“向下”和“向右”的排列位置不同。
因此：
-
每条路径都对应一种选法
-
每种选法也都唯一对应一条路径
这就是一个标准的一一映射关系。
所以路径总数就等于组合数：
C(m+n-2, m-1)
而代码只是在用一种不容易溢出的方式去计算这个组合数而已。
和动态规划解法有什么区别？
这道题最常见的两种做法就是：
1. 动态规划
定义：
dp[i][j] = 到达 (i,j) 的路径数
转移方程：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
优点：
-
思路直观
-
更容易从“网格走法”本身理解
缺点：
-
需要额外数组
-
空间复杂度更高
2. 组合数学
直接把问题转成：
C(m+n-2, m-1)
优点：
-
代码更短
-
空间复杂度更低
-
数学上非常漂亮
缺点：
-
需要先看出问题本质是组合数
所以你这份代码虽然短，但其实比普通 DP 更“高级”一点，因为它抓住了问题最底层的结构。
复杂度分析
时间复杂度
循环次数是：
m - 1
所以时间复杂度是：
O(m)
当然如果把 m 和 n 对称看待，也可以理解成：
O(min(m, n))
的某种组合数计算思路，只不过你这里是按 m - 1 这一边展开的。
空间复杂度
只使用了常数级变量：
-
ans -
up -
down
所以空间复杂度是：
O(1)
这比二维 DP 的 O(mn) 空间复杂度要低很多。
这道题真正想考什么？
这道题表面上看是网格路径题，但本质上考察的是一种非常重要的能力：
第一，能不能从动态规划题里看出数学本质
很多人看到“网格 + 路径数”，就会立刻想到 DP。 这没有错，但如果你能进一步看到：
路径本质上只是固定步数的排列组合
那就说明你对题目的理解更深入了一层。
第二，能不能把组合数写得安全
即使知道答案是组合数，真正写代码时也不能直接暴力算阶乘。 因为中间结果可能会非常大。
而你这段代码采用“边乘边除”的方式来计算组合数，这其实是一个非常值得掌握的小技巧。
总结
这道题的核心思想可以概括成一句话：
从左上角走到右下角，本质上就是在总共 m+n-2 步里，选择 m-1 步向下（或选择 n-1 步向右），因此答案就是组合数。
具体步骤就是：
-
先分析出总步数是：
m + n - 2
-
其中向下步数固定为：
m - 1
-
所以路径总数就是：
C(m+n-2, m-1)
-
用“边乘边除”的方法安全地把这个组合数算出来
这样就能在：
O(m)
的时间复杂度和：
O(1)
的空间复杂度下解决问题。
这是一道非常经典、也非常值得反复理解的题。 因为它会让你真正意识到：
-
很多动态规划题，其实背后还有更深的数学结构
-
如果能抓住问题本质，代码可以变得非常简洁
-
组合数学和算法题并不是割裂的，它们经常会结合在一起出现
把这道题真正吃透之后，再去看：
-
最小路径和
-
不同路径 II
-
杨辉三角
-
网格类 DP 题
你会更容易分辨：哪些题该老老实实做 DP，哪些题其实可以直接转成数学问题。
