Подсчитайте все возможные пути сверху вниз слева направо

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. Использование длинных массивов тоже не работает. В одном из правильных решений формула `Рассчитывать [I] [J] = (количество [I-1] [J] + кол [I] [J-1])% ( (интермедиат) Math.pow (10,9) +7) ; используется! Я не могу понять причину того же.

Answer 1

Требуется m + n - 2 шага, чтобы перейти от верхнего левого к нижнему правому краю сетки mxn, используя только шаги вправо и вниз: m - 1 шаг вправо и n - 1 шаг вниз.Каждый отдельный путь характеризуется определенным выбором того, какой из этих шагов не работает (эквивалентно: какой из этих шагов является правильным).Для этого есть аналитическое решение:

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

Вы можете распознать это как m-1 ^th Биномиальный коэффициент порядка m + n - 2.

Youконечно, не нужно вычислять его таким образом, и на самом деле вам нужно проявлять большую осторожность, если вы хотите это сделать, потому что факториал очень быстро растет * .И именно поэтому я поднимаю этот вопрос: какими бы средствами вы его не вычисляли, результат быстро растет при m, близком к n, довольно быстро выходя за пределы диапазона long - хотя бы в геометрической прогрессии, а не факториально.

В одном из правильных решений формула `count [i] [j] = (count [i-1] [j] + count [i] [j-1])% ((int) Math.pow (10), 9) +7);используется!Я не могу понять причину того же.

Это не будет использовано для правильного решения проблемы, которую вы представили, но я видел модифицированную версию этой проблемы, где это имело бы смысл:тот, где вас просят вычислить результат по модулю 1000000007 , который является именно тем, что делает смущающий вас бит.Я думаю, что видел это в Project Euler, но это могут быть и другие места.Эта вариация проблемы позволяет полностью избежать проблемы непредставимых целых чисел в любой системе, которая имеет 32-битный тип целого числа.

Answer 2

Тестируя с размером квадрата и используя 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