Как доказать корректность DP-перехода, чтобы не ловить WA на крайних случаях?
Часто ДП «вроде правильное», проходит примеры, но падает на скрытых тестах. Подозреваю, что проблема в недоказанном переходе: я не уверен, что перебрал все варианты прихода в состояние. Как системно убедиться, что переход корректен и полон, ДО отправки?
2 ответа
Системная проверка ДП-перехода — это три вопроса к каждому состоянию:
- Определение состояния однозначно? Сформулируй словами, что хранит
dp[...](«минимальная стоимость обработать первые i элементов, закончив в состоянии s»). Если не можешь сформулировать одной фразой — переход почти наверняка дырявый. - Переход полон? Перечисли ВСЕ способы прийти в состояние / уйти из него. Для каждого решения, ведущего к оптимуму, должен существовать хотя бы один разобранный переход. Часто забывают вариант «не брать / пропустить» — отсюда WA.
- Переход корректен? Каждый рассмотренный переход обязан соответствовать допустимому действию (не нарушает ограничений). Лишние переходы дают переоценку.
Ключ — индукция: предполагаешь, что все состояния, от которых зависит dp[i], уже посчитаны верно (по порядку обхода), и доказываешь, что формула даёт верное dp[i]. Если порядок обхода не гарантирует готовность источников — это баг порядка, а не формулы.
Отдельно проверь базу (наименьшие состояния) и крайние случаи: пустой вход, n=1, все элементы равны, ответ = 0/отрицательный. Большинство скрытых WA — именно в базе и крайних случаях, а не в основном переходе.
Мощный практический приём — стресс-тест (брутфорс vs ДП). Пишешь тупой переборный солвер (заведомо верный на малых n), генератор случайных маленьких тестов и сравниваешь ответы в цикле:
for (int t = 0; t < 100000; t++) {
auto test = randomSmallTest();
if (dpSolve(test) != bruteForce(test)) { printTest(test); break; }
}
За минуту это ловит почти все ошибки перехода/базы/границ, которые невозможно увидеть глазами. Когда нашёлся минимальный расходящийся тест — баг локализуется мгновенно. Это надёжнее любого «доказательства в уме» под стрессом контеста.