java - 尝试解决 Leetcode 唯一路径问题时数字太大

Question

我正在尝试解决 Unique Paths来自 LeetCode 的问题。基本上，问题是你得到了一个 m by n 网格，你必须计算从左上角到右下角的路径数量，同时只向下走或对。

我正在做数学方法，这很难弄清楚，但基本公式是这样的:

(m - 1 + n - 1) Choose (min(m - 1, n - 1))，n Choose r 的公式为 n!/(r! * (n-r)!).

这种方法效果很好，但最终阶乘会超过整数限制，因此它会变成负值。我尝试的下一件事是将所有内容更改为 long，但数字再次变得太大，太长了。如何简化数字以使其保持在限制范围内？这是我的代码:

public int uniquePaths(int m, int n) { // The method being called
    return (int) (m == 1 || n == 1 ? 1 : choose((m - 1) + (n - 1), Math.min(m - 1, n - 1)));
}

private long choose(long n, long r) { // Calculated n choose r
    return fact(n) / (fact(r) * fact(n - r));
}

private long fact(long n) { // Calculates factorial of n
    return n == 1 ? 1 : n * fact(n - 1);
}

我知道可以简化它，因为答案是一个整数，因此该数字应该很容易落入 Long.MAX_VALUE 范围内。

Answer 1

在更新代码以使用 Java 的 BigInteger 类后，它被接受了。

import java.math.BigInteger; 

class Solution {
    public int uniquePaths(int m, int n) { // The method being called
        BigInteger mB = BigInteger.valueOf(m);
        BigInteger nB = BigInteger.valueOf(n);
        BigInteger ans =  
                (mB.equals(BigInteger.ONE) || nB.equals(BigInteger.ONE) ? 
                BigInteger.ONE :
                choose(mB.subtract(BigInteger.ONE).add(nB.subtract(BigInteger.ONE)), 
                  mB.subtract(BigInteger.ONE).min(nB.subtract(BigInteger.ONE))));

        return ans.intValue();
    }

    private BigInteger choose(BigInteger n, BigInteger r) { // Calculated n choose r
        return fact(n).divide((fact(r).multiply(fact(n.subtract(r)))));
    }

    private BigInteger fact(BigInteger n) { // Calculates factorial of n
        return n.equals(BigInteger.ONE) ? 
            BigInteger.ONE : 
            n.multiply(fact(n.subtract(BigInteger.ONE)));
    }
}