Динамическое программирование это метод оптимизации многошаговых задач в

Если вы стремитесь к высокоуровневой технической работе. Вы должны пройти собеседование по кодированию-и выйти на первое место. И один верный способ произвести впечатление-это динамическое программирование.
В сегодняшнем специальном гостевом посте Сэм Гэвис-Хьюсон проводит нас через свою формулу решения любой задачи динамического программирования. Убери его, Сэм! Раскрытие информации: Я являюсь партнером курсов Сэма. Хотя ресурсы, упомянутые в этом посте, бесплатны, я могу получить небольшую комиссию. Если вы перейдете по ссылкам ниже и позже купите один из его продуктов. Спасибо!


Когда дело доходит до кодирования интервью, не все темы создаются равными.

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

Но есть и такие темы, где даже самые простые вариации вселяют страх в сердца интервьюируемых повсюду.

Одной из таких тем является динамическое программирование—метод оптимизации. Который программисты могут использовать для ускорения нашего кода при многократном решении одной и той же задачи.

Динамическое программирование

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

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


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

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

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

Этот ответ на переполнение стека хорошо говорит об этом: “Динамическое программирование-это когда вы используете прошлые знания. Чтобы облегчить решение будущей проблемы.”

Некоторые преимущества динамического программирования заключаются в том, что оно экономит время кодирования. Сокращает количество строк кода и ускоряет время обработки алгоритма.

А теперь вот что самое безумное.…

Динамическое Программирование Не должно быть Сложным

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

  • Хотите найти оптимальное решение? На самом деле вам нужно начать с подхода грубой силы.
  • Хотите найти итеративное решение? Вы должны начать с рекурсии.
  • Хотите решить проблему как можно быстрее? Вам нужно замедлить его и идти шаг за шагом.

Итак, если динамическое программирование настолько нелогично, как мы можем эффективно решать эти проблемы?

Для начала давайте посмотрим, как большинство людей готовятся к своим собеседованиям по кодированию:

Они сосредоточены на запоминании решений.

Вместо того чтобы быть стратегом и понимать основные методы. Большинство людей сосредотачиваются на простом запоминании как можно большего количества решений.

Запоминание дает вам быструю и легкую победу. Но проблема в том, что это в конечном счете мешает вам.

Когда вы сосредотачиваетесь на запоминании. Ваша стратегия подготовки к собеседованию становится очень простой: просто пройдите через столько проблем. Сколько сможете.

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

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

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

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

Это ваш план, чтобы добраться до беглости.

Динамическое программирование

Итак, вы начинаете запоминать. Вот один пример набора слов:

“suis”, “es”, “est”, “sommes”, “êtez”, “sont”

Какая связь между этими словами (если вы уже знаете французский, сделайте вид, что вы не знаете его ни на секунду)?

На первый взгляд это не очевидно. Таким образом, если бы вы просто запоминали, вы бы запомнили 6 отдельных слов.

Однако на самом деле между этими словами существует очень тесная связь: это все разные спряжения глагола “быть.”

Если мы посмотрим на переводы, то увидим:

  • “Je suis” – “I am”
  • “Tu es” – “Ты есть”
  • “Elle est” – “Она есть”
  • “Nous sommes” – “Мы”
  • “Vous etez” – “Вы все”

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

Ну и что, если мы могли бы сделать то же самое с динамическим программированием?

Ну, это никогда не произойдет, если мы просто попытаемся запомнить решения различных проблем. Проблема в том, что сходство между этими различными проблемами ЗАКЛЮЧАЕТСЯ НЕ в самом решении.

Сходство между всеми задачами динамического программирования находится в процессе.

Ноутбук и ноутбук

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

Остальная часть этого поста взята из моей бесплатной электронной книги которую вы можете скачать здесь.


Как решить задачи Динамического программирования С помощью Быстрого метода

Какова самая важная характеристика любого успешного собеседника?

У них есть повторяющаяся стратегия.

Именно в этом и заключается БЫСТРЫЙ метод. Это повторяемая стратегия решения любой задачи динамического программирования, независимо от того. Видели вы ее раньше или нет.

Быстрый метод является аббревиатурой для 4 шагов. Необходимых для решения любой задачи динамического программирования:

  1. Find Первое решение
  2. А проанализируйте первое решение
  3. Определите Subproblems
  4. Турна вокруг раствора

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

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

Хватит ждать и начинай учиться! Получите мои 10 советов по обучению себя кодированию.

1. Найдите первое решение

Первый шаг для любой задачи динамического программирования (и шаг. Который большинство людей пропускают) состоит в том. Чтобы найти исходное грубое решение проблемы.

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

Есть несколько ключей, о которых нужно подумать, делая этот шаг, и которые вы должны иметь в виду:

  1. Решение должно быть рекурсивным. Если нет, проблема, вероятно, не является хорошим кандидатом для динамического программирования. Для получения более подробной информации об эффективном создании рекурсивного решения смотрите здесь.
  2. Каждый рекурсивный вызов должен быть самодостаточным. Это означает. Что вы не можете хранить свои результаты в глобальной переменной или передавать переменную результатов в свою функцию. Я часто называю необходимый подход “наращиванием по мере возвращения”, и вы можете узнать больше об этом здесь.
  3. Важно, чтобы мы минимизировали число переменных, которые мы передаем в нашу рекурсивную функцию. Решения динамического программирования полагаются на наличие нескольких рекурсивных вызовов с одним и тем же входным сигналом. И чем больше переменных. Тем меньше входные сигналы будут перекрываться.

Имея в виду эти основные правила. У вас не будет никаких проблем с использованием этого решения грубой силы в БЫСТРОМ методе.

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

2. Проанализируйте первое решение

Это шаг, на котором мы решаем. Можем ли мы на самом деле использовать динамическое программирование для решения проблемы. Для этого мы рассмотрим несколько конкретных вещей.

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

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

Например, если бы мы находили все комбинации входных данных, это дало бы нам временную сложность `O(2n)`. Вы можете прочитать об этом гораздо больше здесь.

Далее, если наше решение на самом деле неэффективно (мы, скорее всего, ищем что-то. Что является экспоненциальным временем или еще хуже. Как неэффективное). Мы хотим посмотреть. Сможем ли мы оптимизировать его с помощью динамического программирования.

Динамическое программирование фактически требует, чтобы мы соответствовали 2 определенным критериям. Если мы этого не сделаем, то мы не сможем оптимизировать нашу проблему с помощью динамического программирования. Однако, если мы это сделаем, мы, вероятно, увидим значительное улучшение.

Это те критерии, которые нам нужно искать:

Оптимальная Субструктура

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

Перекрывающиеся Подзадачи

Именно здесь и происходит реальная оптимизация. Если наша задача имеет перекрывающиеся подзадачи, это означает. Что мы вызываем одну и ту же функцию с точно такими же входными данными несколько раз. Так что мы делаем однообразную работу без всякой причины. Если бы мы кэшировали (или “запоминали”) результаты, мы смогли бы сэкономить много времени.

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

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

Перестаньте ждать и начните учиться! Получите мои 10 советов по обучению себя кодированию.

3. Определите подзадачи

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

Чтобы приблизиться к этому шагу, мы специально рассмотрим наш рекурсивный код и посмотрим. Какие рекурсивные вызовы выполняются. Затем мы хотим определить на простом английском языке, что такое фактическое значение этого рекурсивного вызова.

Например, если мы вычисляем n-е число Фибоначчи, у нас есть 2 рекурсивных вызова, fib(n-1) и fib(n-2). Чтобы определить их на простом английском языке, функция просто возвращает n-е число Фибоначчи. Довольно просто.

Как только мы определили. Что такое подзадачи. Мы также можем запомнить наше рекурсивное решение. Чтобы сделать его более эффективным. Все это означает. Что мы собираемся добавить массив или хэш-карту, которая хранит все значения. Которые мы ранее вычисляли.

Каждый раз. Когда мы делаем вызов функции. Мы будем искать в нашем массиве. Чтобы увидеть. Был ли результат уже вычислен для текущих входных данных. Если это так. То мы можем вернуть его. Фактически ничего не вычисляя. Если нет, мы вычисляем его и затем сохраняем в нашем массиве.

Для получения полного кода и примеров задач загрузите Динамическое программирование для интервью.

4. Переверните решение

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

На этом необязательном заключительном этапе процесса мы возьмем наше рекурсивное решение и превратим его в итеративное.

При динамическом программировании у нас действительно есть два разных варианта:

  • Нисходящее (memoized) решение
  • Решение снизу вверх (табличное)

Нисходящее решение-это рекурсивное решение. Которое мы нашли на предыдущем шаге. Мы называем это нисходящим, потому что мы начинаем с результата цели, который мы пытаемся получить (т. Е. fib(5)), а затем неоднократно разделяем его на более мелкие подзадачи. Пока не достигнем нашего базового случая.

Вместо того. Чтобы начинать с нашего целевого ввода. Мы начинаем с базовых случаев. Мы итеративно вычисляем все большие и большие подзадачи. Пока не достигаем целевого результата.

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

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

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

См. Примеры того, как именно это сделать в моей бесплатной электронной книге Динамическое программирование для интервью

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

Однако это также не то. Чего вы должны бояться. Если вы закрепите свои навыки рекурсии и поймете БЫСТРЫЙ метод. Даже самые сложные задачи динамического программирования могут быть легко решены во время вашего собеседования.


Следующие Шаги: Где узнать Больше О Динамическом Программировании

Хотите узнать больше о динамическом программировании? Ознакомьтесь с этими онлайн-курсами:


Об авторе

Сэм Гэвис-Хьюсон. Основатель Byte by Byte. Помогает инженерам-программистам успешно пройти собеседование на вакансии в ведущих технологических компаниях. Он является автором динамического программирования для интервью, электронной книги. Которая показывает всем. Как преуспеть в динамическом программировании интервью.