Как доказать, что у задачи есть оптимальная подструктура (а не просто угадать DP)?
Мне всё время говорят «у задачи оптимальная подструктура, значит динамика». Но как это реально доказать, а не просто почувствовать? На какой-то задаче я навесил DP, а оно дало WA, потому что подструктура не работала. Как формально проверять?
2 ответа
Оптимальная подструктура означает: оптимальное решение задачи содержит внутри себя оптимальные решения подзадач. Стандартный способ доказательства — «вырезать и вклеить» (cut-and-paste). Берёшь оптимальное решение целой задачи, выделяешь в нём кусок, отвечающий подзадаче, и предполагаешь от противного, что этот кусок не оптимален. Тогда заменяешь его на оптимальное решение подзадачи — общий ответ не ухудшится (а должен был бы стать лучше), противоречие с оптимальностью исходного. Значит, кусок был оптимальным.
Пример с кратчайшим путём: если кратчайший путь s→t проходит через v, то его участок s→v обязан быть кратчайшим путём из s в v — иначе заменили бы его на более короткий и улучшили s→t.
Ключ в том, что подзадачи должны быть независимы: решение одной не должно расходовать ресурс, нужный другой. Где это ломается — там DP по наивному разбиению даёт WA.
Классический контрпример, на котором подструктура НЕ работает: самый длинный простой путь в графе. Казалось бы, длиннейший путь s→t через v состоит из длиннейших s→v и v→t. Но это неверно: эти два куска могут делить вершины, и склейка перестанет быть простым путём. Подзадачи не независимы. Поэтому longest path — NP-трудная, а не DP. Перед тем как писать DP, всегда проверяй: можно ли скомбинировать оптимальные решения подзадач, не нарушив ограничений (без повторов вершин, без превышения ресурса). Если нет — подструктуры нет.