Недавно обсуждали с одним высокогрейдовым программистом — что же такое динамическое программирование (DP)? Книжки по алгоритмам нам говорят, что есть такое вот загадочное программирование, которым решается задача о рюкзаке* (вот решение, запомни) или можно посчитать расстояние Левенштейна (вот решение, вызубри).

*Напомню, что задача о рюкзаке это задача о том, как засунуть в рюкзак набор вещей максимальной ценности, если вместимость рюкзака ограниченна.

При этом обычно не даётся никакого универсального алгоритма, как решить с помощью DP любую задачу. Точнее, алгоритм такой — разбиваем задачу на меньшие подзадачи, решаем их, результаты мемоизируем и собираем ответ для исходной задачи. Похоже на «Разделяй и властвуй», но с неоднократным переиспользованием результатов каждого уровня.

И кажется мне, что сами задачи в полной мере и описывают принцип, потому везде через задачи и обьясняют DP. В чём проблема того же рюкзака? Если мы будем решать задачу жадно (берём на каждой итерации самую дорогую вещь, которая сейчас влазит в рюкзак), то решение может быть неоптимальным. Для примера, есть на полке айфоны и макбуки. Айфон занимает 1 позицию в рюкзаке и стоит 100k. Макбук занимает 4 позиции и стоит 200k. Вместимость рюкзака — 4 позиции. Жадный алгоритм говорит нам взять макбук. Динамическое программирование говорит: представь, что у тебя рюкзак на 1 позицию. Что туда влезет идеальное? А на 2 позиции? А на три? А на 4, что выгоднее — докинуть к максимуму из 3-х позиций ещё один айфон или взять макбук?
Итого DP даёт решение «4 айфона».

Казалось бы, можно такое забрутфорсить на изи, но теперь представим, что на полке у нас айфоны, эпплвотчи, наушники, чехлы, макбуки, аймаки, колонки. А рюкзак большой, но мы должны ещё думать и о максимальном весе.

Т.е. динамическое программирование — это не просто навык написания таких алгоритмов, которые разбивают исходную задачу на более простые части и собирают ответ. Это навык создания подструктур, которые превратят решение в набор перекрывающихся подзадач. И засада в том, что в каждом конкретном сложном случае надо будет придумать такую подструктуру.

Желаю вам избежать DP-задач на собеседованиях.