解决欧拉计划第15题效率问题：20×20网格路径计数

问题背景 #

从2×2网格的左上角出发，仅允许向右和向下移动，到达右下角共有6条路径。那么20×20网格中这样的路径有多少条？

嘿，这个问题其实是组合数学里的经典题，咱们先理清楚背后的逻辑：要从20×20网格的左上走到右下，你一共需要走20次向右、20次向下，总共40步。路径的总数本质上就是**从40步里选20步走向右（剩下的自然是向下）**的组合数，公式是：
$$C(40,20) = \frac{40!}{20! \times (40-20)!}$$

你的代码补全与优化 #

你已经找对了核心方向——用BigInteger处理超大数（毕竟C(40,20)是个非常大的数，普通整数类型根本装不下），不过你的choose方法没写完，我帮你补全并优化了整个代码：

import java.math.BigInteger;

public class GridPathCounter {
    public static void main(String[] args) {
        BigInteger twenty = new BigInteger("20");
        BigInteger totalSteps = twenty.add(twenty);
        System.out.println(choose(totalSteps, twenty));
    }

    // 计算组合数 C(n, k)，用逐步计算法避免超大阶乘
    public static BigInteger choose(BigInteger n, BigInteger k) {
        // 利用组合数对称性：C(n,k) = C(n,n-k)，减少循环次数
        if (k.compareTo(n.subtract(k)) > 0) {
            k = n.subtract(k);
        }
        BigInteger result = BigInteger.ONE;
        for (BigInteger i = BigInteger.ONE; i.compareTo(k) <= 0; i = i.add(BigInteger.ONE)) {
            // 逐步计算：result = result * (n - k + i) / i
            // 这种方式比直接算阶乘更高效，中间不会产生过大的数值
            result = result.multiply(n.subtract(k).add(i));
            result = result.divide(i);
        }
        return result;
    }

    // 如果你坚持想用阶乘实现，完整的factorial方法如下
    public static BigInteger factorial(BigInteger num) {
        BigInteger result = BigInteger.ONE;
        for (BigInteger i = BigInteger.ONE; i.compareTo(num) <= 0; i = i.add(BigInteger.ONE)) {
            result = result.multiply(i);
        }
        return result;
    }

    // 基于阶乘的组合数计算方法
    public static BigInteger chooseWithFactorial(BigInteger n, BigInteger k) {
        return factorial(n).divide(factorial(k).multiply(factorial(n.subtract(k))));
    }
}

小细节说明 #

• 为什么不用直接算阶乘？直接计算40!虽然可行，但逐步计算组合数的方式更高效，中间不会产生过于庞大的数值，能减少内存占用。
• BigInteger是Java专门用来处理任意大小整数的类，完美解决了超大数溢出的问题。
• 利用组合数的对称性，当k大于n/2时，换成n-k来计算，能大幅减少循环次数。

运行这段代码，你就能得到20×20网格的路径总数：137846528820

内容的提问来源于stack exchange，提问作者Ryan Lioy