LeetCode 62. 不同路径 — Rust 实现思路机器人只能向右或向下走总共需要走(m-1)次右移 (n-1)次下移总步数固定。问题等价于在mn-2步中选出m-1步向右 → 组合数C(mn-2, m-1)。也可以理解为路径计数 DP。方法一数学组合数implSolution{pubfnunique_paths(m:i32,n:i32)-i32{let(m,n)(masi64,nasi64);// 利用对称性 C(a, k) C(a, a-k)取较小的 k 减少计算量letkm.min(n)-1;lettotalmn-2;letmutresult:i641;foriin1..k{// result result * (total - k i) / i// 用 C(a, b) C(a, b-1) * (a - b 1) / b 递推resultresult*(total-ki)/i;}resultasi32}}注意要用i64防止中间溢出题目m, n 100C(198, 99)约 9e57 中用i64即可递推过程中每一步整除后都保持是整数。方法二一维 DPimplSolution{pubfnunique_paths(m:i32,n:i32)-i32{let(m,n)(masusize,nasusize);letmutdpvec![1i32;n];// dp[j]到达当前行第 j 列的路径数for_in1..m{forjin1..n{dp[j]dp[j-1];// 上方 dp[j] 左方 dp[j-1]}}dp[n-1]}}技巧第一行和第一列的路径数恒为 1所以初始化为全 1内层循环只需从j 1开始更新。复杂度对比方法时间空间组合数递推O(min(m,n))O(1)一维 DPO(m × n)O(n)关键点递推式C(a, k) C(a, k-1) * (a - k 1) / k每次整除保证整除性因为C(a, k)必为整数且递推过程每一步都恰好整除DP 优化二维数组dp[i][j] dp[i-1][j] dp[i][j-1]压缩为一维滚动数组若考虑更大的m, n可改用u128或逐次乘除python 风格——本题i64足够推荐用方法一代码简洁且最快。
Kimi LeetCode 62. 不同路径 Rust实现
LeetCode 62. 不同路径 — Rust 实现思路机器人只能向右或向下走总共需要走(m-1)次右移 (n-1)次下移总步数固定。问题等价于在mn-2步中选出m-1步向右 → 组合数C(mn-2, m-1)。也可以理解为路径计数 DP。方法一数学组合数implSolution{pubfnunique_paths(m:i32,n:i32)-i32{let(m,n)(masi64,nasi64);// 利用对称性 C(a, k) C(a, a-k)取较小的 k 减少计算量letkm.min(n)-1;lettotalmn-2;letmutresult:i641;foriin1..k{// result result * (total - k i) / i// 用 C(a, b) C(a, b-1) * (a - b 1) / b 递推resultresult*(total-ki)/i;}resultasi32}}注意要用i64防止中间溢出题目m, n 100C(198, 99)约 9e57 中用i64即可递推过程中每一步整除后都保持是整数。方法二一维 DPimplSolution{pubfnunique_paths(m:i32,n:i32)-i32{let(m,n)(masusize,nasusize);letmutdpvec![1i32;n];// dp[j]到达当前行第 j 列的路径数for_in1..m{forjin1..n{dp[j]dp[j-1];// 上方 dp[j] 左方 dp[j-1]}}dp[n-1]}}技巧第一行和第一列的路径数恒为 1所以初始化为全 1内层循环只需从j 1开始更新。复杂度对比方法时间空间组合数递推O(min(m,n))O(1)一维 DPO(m × n)O(n)关键点递推式C(a, k) C(a, k-1) * (a - k 1) / k每次整除保证整除性因为C(a, k)必为整数且递推过程每一步都恰好整除DP 优化二维数组dp[i][j] dp[i-1][j] dp[i][j-1]压缩为一维滚动数组若考虑更大的m, n可改用u128或逐次乘除python 风格——本题i64足够推荐用方法一代码简洁且最快。