Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS. Часто встречаю в интернете такое: «Мне дали на 4-м туре собеседования в Яндексе задачу динамического программирования — уууу — какая сложная была!», «Сейчас крупнейшие зарубежные компании на собеседовании сразу дают динамику, чтобы отсеять слабых программистов». Из-за устоявшихся стереотипов такие задачи считаются очень сложными. Предполагается, что решение их подвластно немногим. Что же это за...
Что такое динамическое программирование? Это метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Все еще не очень понятно? Однако эта хитрость помогает решить многие задачи в разработке быстрее, поэтому начинающим разработчикам стоит в ней разобраться. В гайде подробно рассказываем, про динамическое программирование и приводим примеры задач с динамическим решением. Изучайте!