LeetCode 62. 不同路径 — Rust 实现

思路：机器人只能向右或向下走，总共需要走 (m-1) 次右移 + (n-1) 次下移，总步数固定。问题等价于：在 m+n-2 步中选出 m-1 步向右 → 组合数 C(m+n-2, m-1)。也可以理解为路径计数 DP。

方法一：数学（组合数）

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let (m, n) = (m as i64, n as i64);
        // 利用对称性 C(a, k) = C(a, a-k)，取较小的 k 减少计算量
        let k = m.min(n) - 1;
        let total = m + n - 2;

        let mut result: i64 = 1;
        for i in 1..=k {
            // result = result * (total - k + i) / i
            // 用 C(a, b) = C(a, b-1) * (a - b + 1) / b 递推
            result = result * (total - k + i) / i;
        }
        result as i32
    }
}

注意：要用 i64 防止中间溢出（题目 m, n <= 100，C(198, 99) 约 9e57 中，用 i64 即可，递推过程中每一步整除后都保持是整数）。

方法二：一维 DP

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let (m, n) = (m as usize, n as usize);
        let mut dp = vec![1i32; n]; // dp[j]：到达当前行第 j 列的路径数

        for _ in 1..m {
            for j in 1..n {
                dp[j] += dp[j - 1]; // 上方 dp[j] + 左方 dp[j-1]
            }
        }
        dp[n - 1]
    }
}

技巧：第一行和第一列的路径数恒为 1，所以初始化为全 1；内层循环只需从 j = 1 开始更新。

复杂度对比

关键点

1. 递推式：C(a, k) = C(a, k-1) * (a - k + 1) / k，每次整除保证整除性（因为 C(a, k) 必为整数，且递推过程每一步都恰好整除）
2. DP 优化：二维数组 dp[i][j] = dp[i-1][j] + dp[i][j-1] 压缩为一维滚动数组
3. 若考虑更大的 m, n，可改用 u128 或逐次乘除（python 风格）——本题 i64 足够

推荐用方法一，代码简洁且最快。