Найти общее число путей в матрицу из 0 и 1


Я работаю над программой, которая гласит:

Вам дается 2-мерная матрица с M строками и N столбцами.Вы изначально позиционировали в (0,0), которая является левой верхней ячейки в массиве. Вам разрешается двигаться вправо или вниз. Массив заполняется с 1 и 0. Значение 1 указывает, что можно двигаться по этой ячейке, а 0 означает, что вы не можете двигаться через эту ячейку. Возвращает количество путей от верхней левой ячейки до нижней правой ячейки.(т. е. (0,0)К(М-1,Н-1)). Так как ответ может быть большим, таким образом, вы должны вернуть Анс%(10^9+7).

static int count(int a[][], int i, int j) {
    int rows = a.length;
    int cols = a[0].length;
    if(a[i][j] == 0)  return 0;
    if (i == rows - 1 && j == cols - 1)
        return a[i][j];
    else if (i == rows - 1)
        return a[i][j + 1];
    else if (j == cols - 1)
        return a[i + 1][j];
    else if (a[i][j] == 1)
        return count(a, i + 1, j) + count(a, i, j + 1);
    else
        return 0;
}

Как мы можем улучшить работу этой программы?



1230
1
задан 27 февраля 2018 в 10:02 Источник Поделиться
Комментарии
2 ответа

Рекурсия не рекомендуется. Во-первых, вы, вероятно, в конечном итоге повторяя расчеты для клеток, которые подошли из нескольких путей. Во-вторых, стек вызовов будет так глубоко, как самый длинный путь, и вы могли бы легко врезаться С StackOverflowError на большой лабиринт.

Вместо этого, я рекомендую использовать , построение 2D и таблицы, где каждая запись-число путей из начала в это место. Каждый paths[r][c] вычисляется ровно один раз, и в порядке, который является мягким в кэш.

public static int count(int[][] a) {
int[][] paths = new int[a.length][a[0].length];
if ((paths[0][0] = a[0][0]) == 0) {
return 0;
}
for (int c = 1; c < a[0].length; c++) {
paths[0][c] = a[0][c] * paths[0][c - 1];
}
for (int r = 1; r < a.length; r++) {
paths[r][0] = a[r][0] * paths[r - 1][0];
for (int c = 1; c < a[r].length; c++) {
paths[r][c] = a[r][c] * (paths[r - 1][c] + paths[r][c - 1]);
}
}
return paths[a.length - 1][a[0].length - 1];
}

Вы можете даже построить paths по одной строке за раз, в то время как лабиринт a загружается. Кроме того, можно изменить код, чтобы использовать меньше памяти, так как только две последние строки paths актуальны в любое время. Однако, для простоты, я не сделал здесь: Если вы можете позволить себе держать всю a в памяти, то вы, вероятно, сможете позволить себе еще один 2Д массив того же размера.

1
ответ дан 28 февраля 2018 в 01:02 Источник Поделиться

Вы, вероятно, пересчитав несколько раз клетка. Например, скажем, у вас есть 3х3, где все ячейки 1. Вы сможете рассчитать count(a, 1, 1) дважды: первый раз как часть count(a, 0, 1)и однажды как часть count(a, 1, 0).

Вместо этого вы должны отслеживать эти значения вы уже рассчитали, и вернуть тех, где это доступно. Например:

static int count(int a[][], int i, int j) {
return count(a, i, j, new int[a.length][a[0].length]);
}

static int count(int a[][], int i, int j, int[][] results) {
if (results[i][j] != 0) {
return results[i][j];
}
int rows = a.length;
int cols = a[0].length;
int ret;
if(a[i][j] == 0)
ret = 0;
else if (i == rows - 1 && j == cols - 1)
ret = a[i][j];
else if (i == rows - 1)
ret = a[i][j + 1];
else if (j == cols - 1)
ret = a[i + 1][j];
else if (a[i][j] == 1)
ret = count(a, i + 1, j, results) + count(a, i, j + 1, results);
else
ret = 0;
results[i][j] = ret;
return ret;
}

0
ответ дан 27 февраля 2018 в 10:02 Источник Поделиться