Динамическое программирование: не так страшен чёрт... | OTUS
🔥 Начинаем BLACK FRIDAY!
Максимальная скидка -25% на всё. Успейте начать обучение по самой выгодной цене.
Выбрать курс

Курсы

Программирование
iOS Developer. Basic
-25%
Python Developer. Professional
-25%
Разработчик на Spring Framework
-25%
Golang Developer. Professional
-25%
Python Developer. Basic
-25%
iOS Developer. Professional
-25%
Highload Architect
-25%
JavaScript Developer. Basic
-25%
Kotlin Backend Developer
-25%
JavaScript Developer. Professional
-25%
Android Developer. Basic
-25%
Unity Game Developer. Basic
-25%
Разработчик C#
-25%
Программист С Web-разработчик на Python Алгоритмы и структуры данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Vue.js разработчик VOIP инженер Программист 1С Flutter Mobile Developer Супер - интенсив по Kubernetes Symfony Framework Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-25%
DevOps практики и инструменты
-25%
Архитектор сетей
-25%
Инфраструктурная платформа на основе Kubernetes
-25%
Супер-интенсив «ELK»
-16%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив "SQL для анализа данных"
-16%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Администратор Linux. Виртуализация и кластеризация Нереляционные базы данных Супер-практикум по использованию и настройке GIT IoT-разработчик Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

Динамическое программирование: не так страшен чёрт...

Algo_deep_23.3-5020-f45ccf.png

Часто встречаю в интернете такое: «Мне дали на 4-м туре собеседования в Яндексе задачу динамического программирования — уууу — какая сложная была!», «Сейчас крупнейшие зарубежные компании на собеседовании сразу дают динамику, чтобы отсеять слабых программистов».

Из-за устоявшихся стереотипов такие задачи считаются очень сложными. Предполагается, что решение их подвластно немногим. Что же это за страшный зверь такой — динамическое программирование?

Если разобраться, концептуально тут всё очень просто, и идея этого метода лежит на поверхности. Сперва делаем модель задачи, формализуя её и просто находим решение для параметра модели, равного, скажем, единице. Затем предполагаем, что она решена для параметра, равного N - 1, и, исходя из этого, решаем для N. Те, кто недавно учились в школе знают, что это принцип математической индукции. Не обязательно двигаться с шагом 1, достаточно уметь свести данную задачу к той же задаче, но меньшей размерности.

1-20219-dedf7f.png

Подумав над этой задачей, вы можете решить, что стоит сначала выбрать как можно больше монет максимального номинала для того, чтобы общее количество монет было бы минимальным. Этот способ не всегда ведёт к удаче. Например, у вас есть номиналы 1, 3 и 4 коп. Нужно разменять 10 коп. Если взять максимальные доступные номиналы — 2 раза по 4 коп + 2 раза по 1 коп, это не будет оптимальным решением, поскольку есть решение лучше — 3 + 3 + 4, которое требует всего 3 монеты, а не 4.

Каков общий принцип?

Находим оптимальную комбинацию для “базы” нашей индукции. Для простоты можно взять “вырожденный” случай, когда множество номиналов — пустое и, соответственно, сумма, которую необходимо разменять, равна нулю. Очевидно, для этого нужно 0 монет.

Обозначим нашу функцию количества монет от суммы через coins. То есть, coins(0) = 0. Далее, предположим, вы нашли оптимальную комбинацию для размена суммы n. Это означает, что число монет coins(n), требуемое для размена суммы n, минимальное из возможных.

2-20219-7f2cfa.pngЗная это рекуррентное соотношение, уже можно написать программу для его вычисления, воспользовавшись рекурсией. Для эффективности стоит закэшировать промежуточные результаты, найденные на предыдущих шагах рекурсии.

Аналогичный способ можно использовать для решения такой задачи: сколькими способами можно разменять данную сумму монетами заданных номиналов?

Как только вы видите в условии задачи “Сколько чего-нибудь длины N можно составить?” или “Каково максимальное/минимальное количество чего-нибудь при ограничении на что-то другое?”, смело можете пробовать применять этот метод: скорее всего, он приведёт к успеху.

Подробнее мы рассматриваем этот метод и решаем большое количество задач на динамическое программирование (не только решаем задачи, но и пишем программы!) на нашем курсе Алгоритмы для разработчиков. Присоединяйтесь! Ждём вас!

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться
🎁 Максимальная скидка!
Черная пятница уже в OTUS! Скидка -25% на всё!