Как по виду задачи понять, что это вообще ДП, а не жадность или перебор?
На контесте трачу много времени, пытаясь понять, к какому классу относится задача: ДП, жадность, перебор. Часто пишу жадину, а она проваливается на тесте, и оказывается, что нужно было ДП. Есть какие-то признаки, по которым быстро распознать, что задача на динамику?
2 ответа
Чеклист-маркеры, что задача, скорее всего, на ДП:
- Спрашивают оптимум или количество («минимальная/максимальная стоимость», «сколько способов»), и решение строится последовательно из шагов/предметов/префиксов.
- Есть оптимальная подструктура — ответ для целого выражается через ответы для меньших кусков (префикс, подотрезок, подмножество).
- Подзадачи перекрываются — наивная рекурсия пересчитывает одни и те же состояния много раз (тогда мемоизация спасает).
- Жадность ломается на контрпримере — локально оптимальный выбор не ведёт к глобальному. Признак: «возьмём самое дешёвое/большое сейчас» очевидно проваливается на маленьком тесте.
- Маленькие ограничения по одному из параметров (n ≤ 100, W ≤ 10^4, маска до 2^20) часто намекают на размер таблицы состояний.
Практика: попробуй сформулировать состояние «что я уже обработал + что мне нужно помнить, чтобы продолжить». Если такое состояние компактно (полиномиально/маска) и переход однозначен — это ДП.
Дополню по разнице с жадностью. Жадность работает, когда для оптимума достаточно локального правила выбора и оно доказуемо (exchange argument / матроид). ДП нужно, когда выбор на шаге i влияет на доступность вариантов дальше, и приходится помнить контекст (сколько ресурса осталось, последний взятый элемент и т.п.) — этот контекст и есть состояние ДП. Быстрый тест: придумай 2–3 ручных контрпримера к жадине за минуту. Не ломается — пиши жадину (она проще и быстрее); ломается — переходи к ДП. Не начинай с ДП «на всякий случай», если жадина проходит по ограничениям и доказуема.