Рекурсивный подсчёт числа путей — рабочий код до большого n
Задача про количество путей в сетке (unique paths) или похожая на неё часто получает первое решение через прямую рекурсию: из клетки идём вправо или вниз, суммируем количество путей из обеих соседних клеток.
На маленькой сетке 5x5 такое решение отрабатывает мгновенно. Проблема в том, что рекурсия без мемоизации пересчитывает одни и те же подзадачи многократно — число вызовов растёт экспоненциально с размером сетки.
int countPaths(int row, int col) { if (row == 0 || col == 0) { return 1; } return countPaths(row - 1, col)
- countPaths(row, col - 1); }
На сетке 20x20 это уже сотни тысяч вызовов ради ответа, который вычисляется за один проход динамическим программированием снизу вверх, где каждая клетка считается один раз.
На собесе после такого решения спросят: какая сложность у рекурсии без кэша. Правильный ответ — экспоненциальная, O(2^(n+m)), потому что дерево вызовов не переиспользует поддерево дважды вычисленных клеток. Дальше попросят переписать через таблицу dp[row][col] с накоплением суммы соседних клеток, либо через мемоизацию с кэшем по паре координат.
Прямая рекурсия для задач на сетке — почти всегда сигнал, что дальше попросят посчитать сложность и переписать на dp.
Тренажёр: 600 вопросов, мок с таймером, план повторов
senior·base — что спрашивают на самом деле
В этом посте были ссылки, но мы их удалили по правилам Сетки
