Как оценить число состояний и переходов в ДП, чтобы заранее понять, пройдёт ли по времени?
Часто придумываю ДП, кодирую — и ловлю TLE, потому что не прикинул заранее асимптотику. Как до написания кода аккуратно оценить сложность ДП по числу состояний и стоимости перехода, и с каким бюджетом операций сравнивать на CF (1–2 сек)?
2 ответа
Базовая формула: время ДП = (число состояний) × (стоимость одного перехода).
- Число состояний — произведение размеров всех измерений таблицы. Примеры:
- 1D рюкзак: состояний $O(n\cdot W)$.
- interval DP
dp[i][j]: $O(n^2)$ состояний. - bitmask DP
dp[mask][i]: $O(2^n \cdot n)$. - digit DP
dp[pos][rem][tight]: $O(\text{len}\cdot k\cdot 2)$.
- Стоимость перехода — сколько работы на вычисление одного состояния:
- перебор точки разбиения в interval DP: $O(n)$ → итого $O(n^3)$.
- перебор соседа в TSP: $O(n)$ → итого $O(2^n n^2)$.
- константа (Фибоначчи): $O(1)$ → итого = числу состояний.
Бюджет операций на Codeforces: ориентир $\sim 10^8$–$10^9$ простых операций в секунду (с учётом константы, кэша). Грубо: $10^8$ — спокойно проходит за 1 сек, $10^9$ — рискованно, нужна лёгкая константа.
Пример прикидки: TSP при $n=18$ → $2^{18}\cdot 18^2 \approx 8.5\cdot10^7$ — пройдёт. При $n=22$ → $\approx 2\cdot10^9$ — TLE, нужен другой подход.
Что ещё учитывать помимо голой формулы:
- Память считается отдельно: число состояний × размер ячейки. $2^{20}$
long long= 8 МБ — ок, $2^{24}$ — уже 128 МБ, MLE. Часто память — более жёсткий лимит, чем время. - Константа реализации.
unordered_map-мемоизация в 10–50× медленнее массива. Рекурсия добавляет накладные. Битовые операции и кэш-дружелюбный обход (по строкам) ускоряют в разы. - Сублинейные переходы. Иногда перебор в переходе ускоряется префиксными суммами / деревом отрезков / CHT / монотонной очередью — это снижает $O(\text{переход})$ и весь ДП. Перед кодом полезно прикинуть: «а нельзя ли переход сделать за $O(1)$/$O(\log)$ вместо $O(n)$?»
Правило большого пальца: ограничения в условии (n ≤ ...) намекают на целевую сложность. $n\le 20$ → ждут $2^n$; $n\le 500$ → $O(n^3)$; $n\le 5000$ → $O(n^2)$; $n\le 10^5$ → $O(n\log n)$.