Что такое динамическое программирование?

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

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

Под динамическим программированием понимается метод решения конкретных типов проблем, а именно тех, которые можно разбить на перекрывающиеся подзадачи, которые затем можно оптимизировать. В отличие от разделяй и властвуй, где проблема (например, сортировка слиянием) разбита на более мелкие несвязанные подзадачи, которые решаются, а затем повторно объединяются для решения исходной проблемы, динамическое программирование требует задач с подзадачами, которые связаны или перекрываются. Используя наш пример с шариками, после того, как мы подсчитали нашу первоначальную партию шариков, все следующие итоги были связаны, потому что каждый раз, когда мы получаем больше шариков, мы можем использовать предыдущую сумму и добавлять новую сумму, чтобы обновить нашу текущую сумму, не пересчитывая их заново. . Я расскажу более подробно, используя следующий популярный вопрос на собеседовании по кодированию.

Популярный вопрос на собеседовании по программированию

Представьте, что вы профессиональный вор и ворвались в художественный музей. Охрана сработает только в том случае, если со стены снять соседние картины. Учитывая массив чисел, представляющих стоимость каждой картины, определите максимальную стоимость украденных картин. В следующем массиве значений раскраски: [3,5,6,2,1,8] максимальное значение ограбления будет от 3,6,8 до 17. Если вы хотите попробовать эту задачу прекратите читать здесь, иначе решение находится в следующих разделах.

Настройка проблемы

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

Стоя перед каждой картиной, мы можем либо украсть текущую картину, либо оставить ее. Если мы украдем текущую картину, мы не сможем украсть соседнюю картину (и), и, по сути, у нас будут либо четные, либо нечетные проиндексированные картины. Однако есть еще одна возможность, которую нам нужно учитывать, возьмите следующий массив чисел: [1, 0, 0, 4, 0]. Если бы мы взяли №1, пропустили две картины, а затем взяли №4, мы бы больше не ограничились только нечетными или четными картинами. Если бы мы делали прыжков более двух, мы всегда без необходимости пропускали бы рисунок (если бы мы взяли №1 из предыдущего массива, а затем пропустили три рисунка, чтобы перейти к №5, мы бы пропустили №3 без необходимости).

Последний шаг к настройке нашего решения динамического программирования - связать все наши решения подзадач друг с другом. Итак, чтобы определить наиболее ценное действие, когда мы стоим перед каждой картиной, нам нужно решить, должны ли мы украсть текущую картину и следующую несмежную картину ([1,2,3] # 1 и # 3) или если мы должны пропустить текущую и украсть соседнюю картину. Используя информацию, которую мы обсуждали до сих пор, и чтобы подчеркнуть ценность нашего следующего шага, я включил наивное рекурсивное решение в JavaScript. После нахождения связи между нашими подзадачами мы обычно можем выбрать между подходом сверху вниз с мемоизацией и снизу вверх с табуляцией, чтобы решить нашу проблему, но для полноты картины в этой статье будут рассмотрены оба метода.

Воспоминание (сверху вниз)

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

Табуляция (снизу вверх)

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

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

Окончательное оптимизированное решение

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

Заключение

Подводя итог этапам динамического программирования:

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

2. Мемоизация или табуляция: мы можем выбрать либо рекурсивный подход сверху вниз с мемоизацией, либо метод табуляции снизу вверх. Оба из них придут к аналогичному решению, и их можно будет выбрать, если либо легче концептуализировать, либо если предпочтительна рекурсия.

3. Решение проблемы: после запоминания или табулирования у нас должен быть рабочий алгоритм, но мы также можем сделать любые окончательные оптимизации или настройки, если требуются конкретные результаты.