Динамическое программирование (ДП) — это алгоритмический метод. Его широко используют в информатике и математике для решения сложных задач. Работает он так: сводит к минимуму лишние вычисления и оптимизирует производительность, потому что разбивает большую задачу на более мелкие подзадачи, решает каждую из них и сохраняет результаты.
Рассказываем подробнее об основах ДП, его принципах, приложениях и приводим примеры.
Суть динамического программирования
Динамическое программирование — это когда одну сложную задачу разбивают на более простые подзадачи. Метод основывается на двух ключевых принципах:
- Оптимальная подструктура — оптимальное решение задачи строится на основе оптимальных решений ее подзадач.
- Перекрывающиеся подзадачи — одни и те же подзадачи решают несколько раз.
Динамическое программирование часто путают с рекурсией, но это разные способы решения задач. Рекурсия использует вызовы функций внутри себя. Динамическое программирование сохраняет результаты подзадач, чтобы избежать лишних вычислений.
Основные принципы динамического программирования
Есть два принципа, на которых основывается динамическое программирование. Выбор зависит от специфики задачи и требований к производительности.
Оптимальная подструктура
Принцип оптимальной подструктуры такой: оптимальное решение задачи получают, когда объединяют решения ее подзадач. Эта характеристика решающая в ДП, потому что позволяет систематизировать задачу.
Перекрывающиеся подзадачи
Динамическое программирование использует тот факт, что многие подзадачи повторяются в процессе решения более масштабной задачи. Из-за того, что результаты в перекрывающихся подзадачах сохраняются, ДП позволяет избежать лишних вычислений — значительно сокращает время на большую задачу.
Преимущества и недостатки динамического программирования
У метода динамического программирования есть ряд преимуществ. Например, повышение эффективности и снижение сложности вычислений. Но есть и недостатки.
| Преимущества | Недостатки |
| Сокращает временные затраты | Увеличивает использование памяти |
| Позволяет избежать избыточных вычислений | Более сложный в реализации |
| Оптимизирует процесс решения проблем | Нужно понимать структуру проблемы |
Применение динамического программирования
Динамическое программирование универсально, подходит для разных областей. Рассмотрим несколько примеров.
Задача о рюкзаке
Задача в следующем: нужно выбрать оптимальный набор предметов. У каждого предмета есть определенные вес и значение. Важно уложить в воображаемый рюкзак как можно больше ценных вещей, но не перебрать по весу, так как объем рюкзака ограничен. Как при полете на лоукостере: «упаковать» максимум ценных вещей и не превышать по весу.
Пример:
В ручную кладь можно пронести рюкзак весом до 5 килограммов.
У нас есть следующие предметы ручной клади:
- ноутбук: весит 2 килограмма и стоит 3 очка важности;
- книга: весит 3 килограмма и стоит 4 очка важности;
- куртка: весит 4 килограмма и стоит 5 очков важности;
- фотоаппарат: весит 5 килограммов и стоит 6 очков важности.
Вопрос:
Какие предметы нужно взять в ручную кладь, чтобы их общая важность была самой высокой, а вес не превышал 5 килограммов?
Решение:
Если мы возьмем ноутбук (2 кг, 3 очка важности) и книгу (3 кг, 4 очка важности), то их общий вес будет 2 + 3 = 5 килограммов, а важность 3 + 4 = 7 очков.
Если мы возьмем фотоаппарат (5 кг, 6 очков важности), то вес будет 5 килограммов, а важность 6 очков.
Получается, что выгоднее всего взять ноутбук и книгу, потому что их общая важность 7 очков, а это больше, чем важность фотоаппарата (6 очков).
Динамическое программирование — востребованный навык, который пригодится и в жизни, и в новой карьере. Начните изучать его уже сегодня на курсе «Python-разработчик». Получите высокооплачиваемую профессию и меняйте жизнь к лучшему.
Последовательность Фибоначчи
Последовательность Фибоначчи — классический пример ДП. Вместо рекурсивного пересчета чисел Фибоначчи динамическое программирование сохраняет ранее вычисленные значения — это помогает избежать избыточных вычислений. То есть каждое новое число рождается из двух предыдущих.
Пример:
Следующее число в последовательности получается сложением двух предыдущих чисел.
Начнем с двух чисел: 0 и 1.
- Следующее число: 0 + 1 = 1.
- Следующее число: 1 + 1 = 2.
- Следующее число: 1 + 2 = 3.
- Следующее число: 2 + 3 = 5.
- Следующее число: 3 + 5 = 8.
И так далее.
Последовательность Фибоначчи выглядит так:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Каждое число появляется, когда мы складываем два предыдущих числа.
Какие будут следующие числа в последовательности?
Ответ:
После 34 идет 21 + 34 = 55.
После 55 идет 34 + 55 = 89.
И так — бесконечное количество раз.
Редактировать проблему расстояния
Задача о расстоянии редактирования, или расстоянии Левенштейна, определяет минимальное количество операций, которые нужны, чтобы преобразовать одну строку в другую.
У нас есть два слова, и мы хотим понять, насколько они похожи. Для этого мы используем редактирующее расстояние. Это число показывает, сколько изменений нужно сделать, чтобы одно слово превратилось в другое. Работает это так.
Вставка: добавить букву.
Удаление: убрать букву.
Замена: заменить одну букву на другую.
Пример:
У нас есть слова «кот» и «котик». Нам нужно превратить «кот» в «котик».
- Вставка: добавляем «и» в конце слова «кот» — теперь у нас «коти».
- Вставка: добавляем «к» в конце слова «коти» — теперь у нас «котик».
Мы сделали 2 вставки, чтобы превратить «кот» в «котик».
Другой пример:
У нас есть слова «кот» и «котенок». Давайте посмотрим, как можно превратить «кот» в «котенок».
- Вставка: добавляем «е» после «т» — теперь у нас «коте».
- Вставка: добавляем «н» после «е» — теперь у нас «котен».
- Вставка: добавляем «о» после «н» — теперь у нас «котено».
- Вставка: добавляем «к» в конце слова «котено» — теперь у нас «котенок».
Мы сделали 4 вставки, чтобы превратить «кот» в «котенок».
Редактирующее расстояние между «кот» и «котик» равно 2, потому что мы сделали 2 изменения.
Матричное цепное умножение
Это метод, который помогает найти лучший порядок умножения нескольких матриц, чтобы минимизировать количество вычислений. Здесь используют специальную таблицу, или матрицу, чтобы запомнить минимальные количества операций для разных подзадач, и после комбинируют эти решения, чтобы найти общее наименьшее количество операций.
Пример:
Матрицы — это коробки, а их размеры — это количество предметов внутри.
Есть три матрицы:
- A (2 x 3),
- B (3 x 4),
- C (4 x 2).
Есть два способа умножить их:
- (AB)C,
- A(BC).
Способы умножения:
- (AB)C:
Сначала умножаем A и B. Это займет 2 x 3 x 4 = 24 операции.
Потом умножаем результат (AB) на C. Это займет 2 x 4 x 2 = 16 операций.
Всего: 24 + 16 = 40 операций. - A(BC):
Сначала умножаем B и C. Это займет 3 x 4 x 2 = 24 операции.
Потом умножаем A на результат (BC). Это займет 2 x 3 x 2 = 12 операций.Всего: 24 + 12 = 36 операций.
Выбор наилучшего порядка: второй способ A(BC) требует всего 36 операций, это меньше, чем 40 операций для первого способа (AB)C. Значит, лучше сначала умножить B и C, а потом умножить результат на A.
Как работает динамическое программирование
Есть два основных подхода динамического программирования. Основное отличие: нисходящий подход идет от большой задачи к мелким подзадачам, а восходящий — от мелких подзадач к большой задаче.
Нисходящий подход
Нисходящий подход, или запоминание, нужен, чтобы избежать повторных вычислений. Это рекурсивное решение и сохранение результатов подзадач. Метод интуитивно понятен и прост для начинающих.
Нисходящий подход — начинают с большой задачи и делят ее на мелкие части.
Восходящий подход
Восходящий подход, или составление таблиц, предполагает решение всех подзадач. Этот метод часто эффективнее с точки зрения использования памяти. А еще быстрее при решении определенных задач.
Восходящий подход — начинают с мелких частей и собирают их в большую задачу.
Использование таблиц в динамическом программировании
Таблицы необходимы в ДП, чтобы хранить промежуточные результаты для исключения избыточных вычислений. Эти таблицы — различные состояния и подзадачи. Они гарантируют, что каждая подзадача будет решена только один раз, а ее результат используют повторно.
| Проблема | Представление состояния | Оптимальная подзадача | Промежуточные результаты |
| Задача о рюкзаке | Предметы, вес | Максимальная стоимость | Сохранены в таблице |
| Последовательность Фибоначчи | N | Fibonacci(N-1) + Fibonacci(N-2) | Сохранены в таблице |
| Задача о редактировании текста | Строка 1, строка 2 | Минимальные операции | Сохранены в таблице |
Главное о динамическом программировании
- Динамическое программирование — это метод решения задач, когда сложную задачу разбивают на более простые подзадачи и сохраняют результаты. Это помогает избежать лишних вычислений.
- Основные преимущества динамического программирования — возможность снизить сложность вычислений и повысить производительность за счет исключения избыточных вычислений.
- С помощью задач динамического программирования можно решить задачи оптимизации, задачи кратчайшего пути, задачи с рюкзаком и многие другие.
- Начать изучение стоит с простых задач и примеров, изучите пошаговые руководства и используйте визуализации для лучшего понимания.
Добавить комментарий