Итеративное и рекурсивное не будет иметь заметного различия в производительности.
Вам нужно сделать так, чтобы код запомнил , чтобы вы не делали один и тот же расчет несколько раз.
Для иллюстрации: в матрице 3x5 вы будете ходить так:
X → X → X → X → X
↓ ↓ ↓ ↓ ↓
X → X → X → X → X
↓ ↓ ↓ ↓ ↓
X → X → X → X → X
Заменив X
на количество раз, которое getAllPaths
будет вызываться для этой координаты, вы получите:
1 → 1 → 1 → 1 → 1
↓ ↓ ↓ ↓ ↓
1 → 2 → 3 → 4 → 5
↓ ↓ ↓ ↓ ↓
1 → 3 → 6 → 10 → 15
Как видите, без напоминания координата 4,2 вызывается 15 раз. Это очень плохо для производительности. Если результат был сохранен, он делает рекурсивные вызовы только один раз, вы получите гораздо лучшую производительность.
Я оставлю это вам в качестве упражнения, чтобы узнать больше о запоминании, чтобы вы могли применить его кВаш код.
ОБНОВЛЕНИЕ
Цитирование Википедии:
Заметки - это метод оптимизации, используемый в основном для ускорения компьютерных программ с помощьюхранение результатов дорогостоящих вызовов функций и возвращение кэшированного результата при повторном вводе тех же данных.
Итак, вам необходимо кэшировать результаты вызова метода, а это означает, что вам нужен кеш того же самогоРазмер как лабиринт.
private static int getAllPaths(int[][] maze, int row, int col) {
int[][] cache = new int[maze.length][maze[0].length];
for (int i = 0; i < cache.length; i++) {
Arrays.fill(cache[i], -1);
}
return getAllPaths(maze, cache, row, col);
}
private static int getAllPaths(int[][] maze, int[][] cache, int row, int col) {
// Check cache
if (cache[row][col] != -1)
return cache[row][col];
// Normal logic
int paths;
if (maze[row][col] == -1) {
paths = 0;
} else if (maze[row][col] == 2) {
paths = 1;
} else {
paths = getAllPaths(maze, cache, row+1, col) + getAllPaths(maze, cache, row, col+1);
}
// Save result in cache
cache[row][col] = paths;
return paths;
}