Не бойтесь динамического программирования

[lightln2]

Я не боюсь, но опасаюсь задач на DP, потому что сложность в деталях:

• Как конкретно определять подзадачу (например, на строках - dp[i] - это задача на символе i или на префиксе длины i? Будем задавать базовые условия для всех подстрок в один символ или для только пустой строки?)

• Какой брать переход из возможных опций (dp[i] - количество нужных подстрок, заканчивающихся на символе i или принадлежащих префиксу длины i)?

• А если еще и надо восстановить оптимальное рещение, то это еще сильнее усложняет реализацию (будем хранить граф переходов? или потом восстановим из таблицы стоимостей?)

Чаще всего все варианты будут работать, но нужна интуиция, чтобы понять какой приведет к самому короткому и понятному коду без ошибок. Если кто-то знает какие-то эвристики, расскажите!

А мое любимое объяснение DP - лекция из цикла MIT “введение в алгоритмы” авторства Эрика Демайна - очень известный в мире computer scienсе чувак, автор структуры Tango Trees и доказавший, что тетрис NP-полон. Он подробно рассказывает именно о том, какие характеристики задачи делают ее dp, и как от них перейти к формуле.

[wataru]

Но его можно применять только при двух условиях:
...
Перекрывающиеся подзадачи.

Вовсе нет. Эта мысль много где бездумно повторяется, но это вообще не обязательно. ДП все еще будет отлично работать. Например, найти глубину дерева, или подсчитать "хеш" дерева для проверки изоморфизма.

Да, в этом случае граф вызовов будет деревом и мемоизация по сути не нужна, но мемоизация - это лишь деталь реализации, оптимизация. Суть из рекуррентного соотношения остается.

Другие мои 5 копеек:

Динамическое программирование очень полезно формализовывать. Так понятнее, что решение работает, его так легче придумывать.

Вам надо определить:

1) Множество состояний и рекуррентное соотношение. Или же множество задач и как задача решается через подзадачи.

2) База - какие-то состояния имеют фиксированный ответ

3) Ответ. Где ответ на изначальную задачу. Не всегда задача как она есть является одной из подзадач. Иногда в решении вы вводите какие-то новые параметры, которых в условии изначальной задачи нет.

[TimurZhoraev]

Учёт предыдущих состояний даже с переключаемыми весами это фактически некий аналог БИХ-фильтра и там скорее задача уже на устойчивость пути/решения.

[heartdevil]

Я думаю, вы сильно опустили то, что опускать как раз и не нужно. Это как научиться рисовать сову. Надо же только два овала нарисовать, а дальше все просто. Динамическое программирование -- на мой взгляд, одна из самых трудных тем, если не самая трудная. Вся проблема как раз и кроется в том, а как же определять подзадачи. Как просчитать все эти кейсы. Ну и как это все потом реализовать. Это на ваших примерах все просто и гладко получается. А чуть шаг в сторону сделать и уже проблемы с нехваткой состояний или криво подсчитанными состояниями. А часто вообще даже в упор не видно как это все применить, даже если тебе в лоб предъявят, что вот это динамическим программированием решается.

[denorlov]

Расскажите, приходилось ли кому-то решать какую-то практическую задачу с применением ДП? Не leetcode, не поступление в школу, Уни, ШАД, на работу... Именно использовать в реальном рабочем процессе.

[wataru]

Мне приходилось, аж много раз. При реализации пакетизации h264 битстрима: по спецификации там есть режим, что энкодер выдает несколько кусков, и их нельзя резать дальше при распихивании этого по пакетам. Странная идея, но так придумали кучу лет назад, а нам это реализовывать. Можно несколько кусков целиком засунуть в очередной пакет. Переставлять куски, очевидно, тоже нельзя. Надо чтобы эти группы не превышали лимит размера пакета, было как можно меньше пактов, а максимальный пакет был как можно меньше. Без последнего ограничения задача решается тупой жадностью: заполняем пакет, пока туда влезает. Потом начинаем следующий, и так пока куски не кончатся. Но так получаются очень разные пакеты и это плохо для выдерживания пропускной способности сети. Хотелось бы решить задачу с ним. С этим дополнительным условием задача решается через ДП.

Потом, писал для себя утилиту. Было это в старые времена, когда интернет был не безлимитный и за сериальчиками все ходили в гости с жесткими дисками, да качали из локальных сеток. Но место на жестких дисках ограниченно, поэтому сериалы резали на CD а потом и DVD. Десятки, сотни дисков. И опять задача - хотелось бы как-то более эффективно диски использовать. При этом есть всякие естественные ограничения: вроде файлы серий надо записывать подряд, сериал может быть по нескольким дискам, но подряд, чтобы эти диски в стопке рядом лежали. Чтобы когда решишь посмотреть, взять несколько дисков и подряд их вставлять в привод. В итоге навороченная задача о рюкзаке получилась. Моя утилита диски довольно хорошо упаковывала, гораздо лучше чем я руками это делал.

Потом, это применяется в индустриальной оптимизации. Мою программу-курсовую никуда не пристроили, конечно, но знаю, что в моем университете разработали программы и они крутится на производстве фанеры, досок и чего-то еще. По заказам размеров выдает как и что раскраивать, чтобы было как можно меньше отходов. И там помимо методов решения задач линейного программирования в частности вылезает именно динамическое программирование как подзадача.

Ну и почти любой поиск пути в графе, который весьма часто встречается и реализуется алгоритмом Дейкстры - по сути является ДП.

[lightln2]

Многие, кто работают в гугле/яндексе пишут дп регулярно. Но конкретно

использовать в реальном рабочем процессе

Вы это делаете каждый день, когда выполняете git diff - он основан на алгоритме Майерса, варианте Longest Common Subsequence Problem, являющегося классикой DP!