如何在不修改int[][]类型的前提下正确计算15行帕斯卡三角？

嘿，这个问题我之前也碰到过，其实不用修改int[][]数组的类型就能解决——问题根本不在数组本身，而是你计算组合数的方式导致了中间值溢出！

问题根源 #

你当前用阶乘公式C(n,k) = n!/(k!*(n-k)!)计算组合数，但虽然最终的帕斯卡三角值（比如第15行最大的C(14,7)=3432）远小于int的最大值2147483647，但计算阶乘时，fac(13)就已经超出int范围了（13!是6227020800，远大于2147483647），溢出后的错误值再参与除法，自然得不到正确结果。

解决方案一：直接利用帕斯卡三角的递推规则构建数组 #

帕斯卡三角本身有个天然的递推关系：

• 每一行的首尾元素都是1
• 中间的每个元素等于上一行相邻两个元素的和

这种方式完全不会有溢出问题，因为每一步都是加法运算，而且结果本身就在int范围内。修改后的代码如下：

public static void main(String args[]) {
    int[][] bino = new int[15][]; // 保持原数组类型不变
    // 初始化每一行的长度并填充数值
    for(int i = 0; i < bino.length; i++) {
        bino[i] = new int[i + 1];
        // 设置首尾元素为1
        bino[i][0] = 1;
        bino[i][i] = 1;
        // 计算中间元素：上一行相邻两数之和
        for(int j = 1; j < i; j++) {
            bino[i][j] = bino[i-1][j-1] + bino[i-1][j];
        }
    }
    
    // 验证打印
    for(int[] row : bino) {
        for(int num : row) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

解决方案二：修改组合数计算方式，避免阶乘溢出 #

如果你坚持要保留nOverk方法，可以换一种组合数计算逻辑：利用C(n,k) = C(n,k-1) * (n - k + 1) / k的递推公式，或者直接分步计算分子分母，边乘边除（因为组合数是整数，每一步都能整除），这样中间结果不会溢出。

修改后的nOverk和main代码：

public static void main(String args[]) {
    int[][] bino = new int[15][]; 
    for(int i = 0; i < bino.length; i++) {
        bino[i] = new int[i + 1]; // 先初始化每一行的长度
        for(int j = 0; j < bino[i].length; j++) {
            bino[i][j] = nOverk(i, j);
        }
    }
}

public static int nOverk(int n, int k) {
    // 优化：C(n,k) = C(n, n-k)，取较小的k减少计算次数，避免不必要的运算
    k = Math.min(k, n - k);
    int result = 1;
    for(int i = 1; i <= k; i++) {
        // 先乘后除，保证每一步结果都是整数，不会溢出
        result = result * (n - k + i) / i;
    }
    return result;
}

为什么这两种方法可行？ #

不管哪种方式，核心都是避免计算超大的阶乘中间值，直接计算最终的组合数——而帕斯卡三角前15行的所有数值都远小于int的最大值，所以用int数组完全能存下，只是之前的计算路径错了导致溢出。

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