Прежде чем перейти к обсуждению динамического программирования, давайте рассмотрим наши повседневные проблемы. Мы прилагаем много усилий, чтобы найти решение нашей проблемы, но есть простые и легкие способы их решения. Одна из стратегий состоит в том, чтобы получить проблему и разделить ее на более мелкие подзадачи и снова разделить, пока не будет получена меньшая подзадача, а затем найти решения этих более мелких подзадач с помощью перекрывающихся подзадач, благодаря чему найти решение для главного. проблема. Чтобы получить четкое представление, рассмотрите реальную жизненную проблему и разделите ее следующим образом.
- В чем проблема
- в чем причина этой проблемы
- как решить эту проблему
- как использовать этот путь и решить эту проблему
Теперь найдите ответы на все вышеперечисленные подзадачи по отдельности, а затем вы найдете ответ на основную проблему.
«Это четыре благородные истины, провозглашенные Господом Буддой».
В следующей части мы собираемся применить эту стратегию к задачам программирования. Эта стратегия называется динамическим программированием.
Динамическое программирование (также известное как DP) — очень мощная техника для решения конкретных задач программирования. По сути, это не решение проблемы, а стратегия, которую мы можем использовать для решения проблем. Рабочий процесс выглядит следующим образом
- Внимательно прочитайте и наблюдайте за проблемой
- разделить эту проблему на более мелкие подзадачи
- Снова разделите эти подзадачи на более мелкие подзадачи, пока не получите базовый случай.
- Затем определите перекрывающиеся похожие подзадачи и используйте их при необходимости.
- решить основную проблему, решив эту подзадачу
Я знаю, что вы немного запутались, но не волнуйтесь, прежде чем переходить к примерам, сначала мы должны понять следующие концепции.
Рекурсия
Процесс, в котором функция прямо или косвенно вызывает саму себя внутри функции, называется рекурсией, а соответствующая функция называется рекурсивной функцией.
Мемоизация
Мемоизация — это метод повышения производительности рекурсивных алгоритмов. В основном, когда мы используем рекурсию, мы можем найти похожие подзадачи, и вычисление ответа на эту подзадачу снова и снова неэффективно. Таким образом, мы можем сохранить этот ответ в подходящей структуре данных, а затем снова использовать это значение, когда оно понадобится. Это процесс запоминания.
Оптимальная основа
Говорят, что алгоритм имеет оптимальную подструктуру, если оптимальное решение может быть построено из оптимальных решений его подзадач. Что мы разделяем проблему на подзадачи и находим решение для них оптимальным способом, а затем, наконец, используя эти решения, мы можем найти решение главной проблемы оптимальным образом.
например: Жадный алгоритм
Перекрывающиеся подзадачи
когда мы решаем проблему, используя подзадачи, мы можем снова и снова находить одну и ту же подзадачу, а вычисления снова и снова неэффективны. Таким образом, мы можем определить эти перекрывающиеся подзадачи, сохранить их в подходящей структуре данных и использовать, когда это необходимо снова. Это концепция перекрывающихся подзадач
решить задачу динамического программирования
Как я уже говорил ранее, это стратегия для решения алгоритма. DP - это метод решения алгоритма оптимальным и более быстрым способом. Рассмотрим поэтапно
Рассмотрим функцию Фибоначчи (очень распространенная проблема). Фибоначчи — это последовательность чисел, и мы можем вычислить nе число, сложив два предыдущих числа
Определите, является ли это проблемой DP
Все задачи динамического программирования удовлетворяют свойству перекрывающихся подзадач и свойству оптимальной подструктуры. Как только мы наблюдаем эти свойства в данной задаче, мы можем сказать, что она может быть решена с помощью ДП.
В приведенной выше функции Фибоначчи n=6 есть три F1, пять F2, три F3 и два F4. Есть перекрывающиеся подзадачи
Есть два оптимальных свойства подструктуры. это F1 и F0, используя эти оптимальные свойства, мы можем вычислить все остальные дополнительные свойства и, наконец, главную проблему.
Теперь мы можем определить, что это проблема DP.
разделить эту проблему на более мелкие подзадачи
Разделите это n = 6 функций Фибоначчи на меньшие подзадачи. Вы можете видеть дерево выше, и каждый узел представляет собой меньшую подзадачу. Мы можем назвать это состоянием, потому что переходим к более высоким узлам (состояниям), используя более низкие узлы (состояния). Обычно мы путешествуем из одного штата в другой.
Затем определите перекрывающиеся похожие подзадачи
Мы можем идентифицировать перекрывающиеся подзадачи, как я описал ранее.
Сохраните это в подходящей структуре данных
Мы можем сохранить эти перекрывающиеся проблемы в структуре данных, такой как массив, и когда нам снова понадобится это значение, мы сможем получить к нему доступ, а не вычислять его. Это называется Memoization (описано ранее), поэтому мы используем метод сверху вниз для решения этой проблемы.
решить основную проблему, решив эту подзадачу
Хорошо, теперь мы собираемся решить это шаг за шагом.
Сначала мы выбрали F6, потому что это метод сверху вниз. Чтобы найти F6, нам нужно найти F5 и F4 и снова. Чтобы найти F5, нам нужно найти F4 и F3 и так далее, чтобы найти все это, мы должны перейти к базовому случаю, то есть F1 и F0. Теперь мы можем найти использование массива размером 7 и сохранить F1 и F0, а также найти F2 и сохранить его в массиве и так далее. Имейте в виду, когда мы повторно используем предварительно вычисленное значение, мы используем этот массив для получения этого значения.
Мы используем рекурсию для этого процесса, и вы можете видеть это в следующем алгоритме
Резюме
Динамическое программирование (DP) — очень мощная техника, которую мы можем использовать для решения алгоритмов. Используя этот метод, мы можем легко и эффективно решить
DP — это продвинутый метод программирования, и чтобы стать продвинутым программистом, вы должны знать и иметь опыт динамического программирования. Вы можете найти больше проблем в hackerrank, так что найдите это и сделайте это.
