Java中如何避免long类型溢出？网格路径计算问题求解

原代码 #

public static long linearCountWays(int rows, int cols){
    // count grid ways in linear time

    // total permutations (ways) = (rows-1+cols-1)!;
    // repeating permutations (ways) = (rows-1)!*(cols-1)!
    // total ways = total ways / repeating ways

    // will return wrong answer for greater n/m whose factorial overflow the range of long. How can we solve this?

    return factorial(rows+cols-2) / (factorial(rows-1)*factorial(cols-1));
}

问题描述 #

我编写了这段Java代码用于计算n×m网格中从(0, 0)到(n-1,m-1)的可行路径数，算法为线性时间复杂度。但当n或m取值较大时，阶乘运算会超出long类型范围，导致返回错误结果。

示例：输入n=15、m=15时，递归方法（时间复杂度O(2^(n+m))）能得到正确结果40116600，但效率过低无法接受；调用linearCountWays方法却返回错误值1455。请问如何在Java中解决该溢出问题？

解决方案 #

方法1：使用BigInteger处理大整数

Java的BigInteger类支持任意大小的整数运算，完全不会出现溢出问题。我们可以通过分步计算组合数来优化效率，无需计算完整的大阶乘：

import java.math.BigInteger;

public static BigInteger linearCountWaysBigInteger(int rows, int cols) {
    int totalSteps = rows + cols - 2;
    int minSteps = Math.min(rows - 1, cols - 1); // 取较小的步数减少循环次数
    BigInteger result = BigInteger.ONE;

    // 分步计算组合数 C(totalSteps, minSteps)
    for (int i = 1; i <= minSteps; i++) {
        result = result.multiply(BigInteger.valueOf(totalSteps - minSteps + i))
                      .divide(BigInteger.valueOf(i));
    }
    return result;
}

调用这个方法时，直接返回的BigInteger可以转换为字符串输出，或者用longValue()转成long（如果结果在long范围内）。

方法2：优化计算逻辑，避免提前溢出

如果不想引入BigInteger，可以通过分步乘除的方式计算组合数，保证每一步的结果都是整数，最大程度减少溢出风险（适用于rows和cols不是特别大的场景，比如totalSteps≤62时，long能容纳结果）：

public static long linearCountWaysOptimized(int rows, int cols) {
    int totalSteps = rows + cols - 2;
    int minSteps = Math.min(rows - 1, cols - 1);
    long result = 1;

    // 利用组合数性质分步计算，每一步先乘后除保证整除
    for (int i = 1; i <= minSteps; i++) {
        result = result * (totalSteps - minSteps + i) / i;
    }
    return result;
}

比如输入n=15、m=15时，这个方法能正确返回40116600，不会出现溢出。

内容的提问来源于stack exchange，提问作者Aashif Ali