Сигнал задачи
Когда применять
Когда состояние естественно задаётся границами отрезка, подмножеством небольшого множества или ответом внутри поддерева.
Как выбрать подход
- Интервальное DP подходит, если решение [l, r] строится из меньших вложенных интервалов или выбора последнего разбиения.
- Битмасочное DP применимо при небольшом числе объектов, когда маска полностью описывает уже выбранное подмножество; дополнительная координата хранит последний объект или ресурс.
- Древесное DP вычисляет состояние вершины после состояний детей; объединение детей должно явно описывать, что уже учтено.
- Оптимизация памяти допустима только после проверки зависимостей: перезапись слоя не должна уничтожать значения, нужные следующим переходам.
Сложность
- Типичное интервальное DP с перебором точки разбиения: O(n³) времени и O(n²) памяти; без перебора разбиения конкретная рекуррентность может дать O(n²).
- Битмасочное DP: обычно O(2ⁿ · n) или O(2ⁿ · n²) времени и O(2ⁿ) либо O(2ⁿ · n) памяти — в зависимости от наличия последней вершины в состоянии.
- Древесное DP: O(n) для константного состояния и перехода на ребро; с рюкзачным объединением состояний стоимость может вырасти до O(n²) или зависеть от лимита ресурса.
Границы и ошибки
- Неопределённый смысл состояния приводит к двойному учёту при разбиении интервала или слиянии поддеревьев.
- Неверный порядок длин интервалов или масок читает ещё не вычисленные состояния.
- 2ⁿ ограничивает битмасочное DP и по времени, и по памяти; одна дополнительная размерность часто становится решающей.
- Рекурсивный обход глубокого дерева может переполнить стек; родитель должен быть исключён из списка детей.