实际上比较合适的方法是 DP
因为这里又是一个计算方案数的情况，以及每次只会从上方或者左侧转移过来
不过这里第一时间想到的是组合数的解法
比较我们能想到答案是 \(\frac{(n + m - 2)!}{(n - 1)!(m - 1)!}\)，也就是 \(C^{m - 1}_{n + m - 2}\)
关键就是怎么去计算，因为直接计算会溢出 long long
相对合理一些的方法是边乘边除（但是值比较大的时候感觉仍然是会溢出的，正常应该用 Mod ？）
这样做的前提是我们能够保证每次除的时候是整除
设 total = m + n - 2，我们要算的是 C(total, k)
第 i 步，ans = ans * (total - k + i) / i;
i = 0 时， ans = 1 = C(tot, 0)
假设进入第 i 步之前，ans = C(total, i-1)
那么
\[\begin{aligned}
&ans * \frac{total - k + i}{i} \\
=\ &C(total, i-1) × \frac{total - i + 1}{i} \\
=\ &\frac{total!}{(i-1)! × (total-i+1)!} × \frac{total - i + 1}{i} \\
=\ &\frac{total!}{(i-1)! × (total-i)!} × \frac{1}{i} \\
=\ &\frac{total!}{i! × (total-i)!} \\
=\ &C(total, i)
\end{aligned}
\]
由归纳法可知，结果一定是整数
using i64 = long long;class Solution {
public:int uniquePaths(int m, int n) {int total = m + n - 2;int k = min(m, n) - 1;i64 ans = 1;for (int i = 1; i <= k; ++i) {ans = ans * (total - k + i) / i;}return (int)ans;}
};