Comments 3
Я не боюсь, но опасаюсь задач на DP, потому что сложность в деталях:
Как конкретно определять подзадачу (например, на строках - dp[i] - это задача на символе i или на префиксе длины i? Будем задавать базовые условия для всех подстрок в один символ или для только пустой строки?)
Какой брать переход из возможных опций (dp[i] - количество нужных подстрок, заканчивающихся на символе i или принадлежащих префиксу длины i)?
А если еще и надо восстановить оптимальное рещение, то это еще сильнее усложняет реализацию (будем хранить граф переходов? или потом восстановим из таблицы стоимостей?)
Чаще всего все варианты будут работать, но нужна интуиция, чтобы понять какой приведет к самому короткому и понятному коду без ошибок. Если кто-то знает какие-то эвристики, расскажите!
А мое любимое объяснение DP - лекция из цикла MIT “введение в алгоритмы” авторства Эрика Демайна - очень известный в мире computer scienсе чувак, автор структуры Tango Trees и доказавший, что тетрис NP-полон. Он подробно рассказывает именно о том, какие характеристики задачи делают ее dp, и как от них перейти к формуле.
Но его можно применять только при двух условиях:
...
Перекрывающиеся подзадачи.
Вовсе нет. Эта мысль много где бездумно повторяется, но это вообще не обязательно. ДП все еще будет отлично работать. Например, найти глубину дерева, или подсчитать "хеш" дерева для проверки изоморфизма.
Да, в этом случае граф вызовов будет деревом и мемоизация по сути не нужна, но мемоизация - это лишь деталь реализации, оптимизация. Суть из рекуррентного соотношения остается.
Другие мои 5 копеек:
Динамическое программирование очень полезно формализовывать. Так понятнее, что решение работает, его так легче придумывать.
Вам надо определить:
1) Множество состояний и рекуррентное соотношение. Или же множество задач и как задача решается через подзадачи.
2) База - какие-то состояния имеют фиксированный ответ
3) Ответ. Где ответ на изначальную задачу. Не всегда задача как она есть является одной из подзадач. Иногда в решении вы вводите какие-то новые параметры, которых в условии изначальной задачи нет.
Учёт предыдущих состояний даже с переключаемыми весами это фактически некий аналог БИХ-фильтра и там скорее задача уже на устойчивость пути/решения.
Не бойтесь динамического программирования