计算从左上角到右下角的所有可能路径

Question

任务是计算mXn矩阵从左上角到右下角的所有可能路径，其中每个单元格的约束只能向右或向下移动。

     int[][] count = new int[n][m];
     int i,j;

     for (i = 0; i < n; i++)
         count[i][0] = 1;
     for (i = 0; i < m; i++)
         count[0][i] = 1;

     for (i = 1; i < n; i++)
         for (j = 1; j < m; j++)
             count[i][j] = (count[i - 1][j] + count[i][j - 1]);

     System.out.println(count[n - 1][m - 1]);

上面的代码显示了m和n的大值的错误答案。使用长数组也无法正常工作。在一个正确的解决方案中，公式`count [i] [j] =（count [i-1] [j] + count [i] [j-1]）％（（int）Math.pow（10， 9）+7）;用来！我无法理解同样的原因。

Answer 1

使用正方形尺寸和使用int进行测试，最多可以计算17x17。使用18x18，您将获得数字溢出。

要检测数字溢出，请更改以下行：

count[i][j] = (count[i - 1][j] + count[i][j - 1]);

至：

count[i][j] = Math.addExact(count[i - 1][j], count[i][j - 1]);

以18x18运行然后获得java.lang.ArithmeticException: integer overflow，而17x17打印601080390。

更改为long将限制提高到34x34 = 7219428434016265740，并且35x35失败。

要超越它，请使用BigInteger：

private static void count(int n, int m) {
    BigInteger[][] count = new BigInteger[n][m];
    for (int i = 0; i < n; i++)
        count[i][0] = BigInteger.ONE;
    for (int i = 0; i < m; i++)
        count[0][i] = BigInteger.ONE;
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            count[i][j] = count[i - 1][j].add(count[i][j - 1]);
    System.out.println(n + "x" + m + ": " + count[n - 1][m - 1]);
}

您现在可以计算非常大的尺寸：

public static void main(String[] args) {
    for (int i = 10; i < 150; i+=10)
        count(i,i);
}

产量

10x10: 48620
20x20: 35345263800
30x30: 30067266499541040
40x40: 27217014869199032015600
50x50: 25477612258980856902730428600
60x60: 24356699707654619143838606602026720
70x70: 23623985175715118288974865541854103729000
80x80: 23156006494021191956342707682359261381151378400
90x90: 22880174247360071687155809670095748237789263482394000
100x100: 22750883079422934966181954039568885395604168260154104734000
110x110: 22738029575969641265497648088901902565550598643635116137437818400
120x120: 22820983692956015651850538861400483591556161461874723704379950728024000
130x130: 22985198722890636106807214387141205118592781510195606858610359655612113472140
140x140: 23220197341838572012462842682887166477737842005968501197039194284526789533662125200

Answer 2

通过仅向右和向下步骤从m×n网格的左上角到右下角行进需要m + n - 2步：m - 1步向右，n - 1步降低。每个不同的路径的特征在于特定选择哪些步骤失效（等效地：这些步骤中哪一个是正确的）。有一个分析解决方案：

factorial(m + n - 2) / (factorial(m - 1) * factorial(n - 1))

您可能会认识到m-1次二项式系数为m + n - 2。

当然，你不需要那样计算它，事实上，如果你想这样做，你需要非常小心，因为阶乘增长得非常快。这就是我提出这个问题的原因：通过你计算它的任何方式，结果在接近n的时候迅速增长，超过long的范围很快 - 尽管是指数级的，而不是因子的。

在一个正确的解决方案中，公式`count [i] [j] =（count [i-1] [j] + count [i] [j-1]）％（（int）Math.pow（10， 9）+7）;用来！我无法理解同样的原因。

这不会用于你所提出的问题的正确解决方案，但我已经看到了这个问题的修改版本，它会有意义：你被要求计算结果模数1000000007，这正是这个位这让你很困惑。我想我已经在Project Euler上看过了，但也可能是其他地方。对问题的这种变化允许人们完全避免在具有32位整数类型的任何系统上出现不可表示的整数问题。