尝试解决唯一路径问题时，数字变大

Question

我正在尝试解决LeetCode的Unique Paths问题。基本上，问题是通过m网格给了n，并且您必须计算从左上角到右下角的路径数，而仅向下或向右。

我正在做数学方法，要弄清楚这很复杂，但是基本公式是这样的：

(m - 1 + n - 1) choose (min(m - 1, n - 1))，并且n choose r的公式是n! / (r! * (n-r)!)。

此方法效果很好，但是阶乘最终超出了整数限制，因此变为负数。我接下来要尝试的是将所有内容更改为长整，但是之后数字又变长了。如何简化数字以使其保持在限制之下？这是我的代码：

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

好，我明白了。我需要做的是消除分母中更大的数字。如果r大于n-r，则公式变为：

n * n-1 * n-2 ... * r+1 / (n-r)!

如果n-r大于r，则公式变为：

n * n-1 * n-2 ... * (n-r)+1 / r!

这将使分母中较大的数字变小，n!也变小。最后是我的代码：

public int uniquePaths(int m, int n) { // 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) { // Calculates n choose r
    return r > n - r ? fact(n, r) / fact(n - r) : fact(n, n - r) / fact(r);
}

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

private long fact(long n, long lower) { // Calculates n! with lower bound of lower; that is n * n-1 * n-2 ... * lower+1.
    return n == lower ? 1 : n * fact(n - 1, lower);
}

Answer 2

在更新您的代码以使用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)));
    }
}