Почему наивный рекурсивный счёт C(n,k) даёт TLE и как его ускорить мемоизацией?
Написал C(n,k) прямо по рекуррентте Паскаля рекурсией:
long long C(int n, int k) {
if (k == 0 || k == n) return 1;
return C(n-1, k-1) + C(n-1, k);
}
На маленьких работает, но при n около 30-40 уже TLE. Почему так медленно и как починить, оставив рекурсию?
2 ответа
Наивная рекурсия пересчитывает одни и те же C(n,k) экспоненциальное число раз — дерево вызовов разрастается примерно как сам C(n,k), то есть до ~2^n вызовов. Это та же беда, что у наивного Фибоначчи. При n≈40 это сотни миллиардов вызовов → TLE.
Лечение — мемоизация (запоминаем уже посчитанные значения), сводя число РАЗЛИЧНЫХ подзадач к O(n·k):
const int MAXN = 1001;
long long memo[MAXN][MAXN];
bool done[MAXN][MAXN];
const long long MOD = 1e9 + 7;
long long C(int n, int k) {
if (k < 0 || k > n) return 0;
if (k == 0 || k == n) return 1;
if (done[n][k]) return memo[n][k];
done[n][k] = true;
return memo[n][k] = (C(n-1, k-1) + C(n-1, k)) % MOD;
}
Теперь каждое (n,k) считается один раз. Сложность O(n·k) по времени и памяти. Это эквивалентно табличному заполнению треугольника Паскаля, просто «сверху вниз». Без модуля помни про переполнение при больших n.
Если запросов C(n,k) много и n большое — мемоизация по O(n·k) памяти может не влезть; тогда переходи на предподсчёт факториалов и обратных факториалов (O(n) памяти, O(1) на запрос). Рекурсия с мемоизацией хороша, когда нужны лишь некоторые C(n,k) и n умеренное. И не делай мемоизацию на map для горячего кода — хеширование пары даёт большую константу, массив [n][k] быстрее.