304 читали · 4 года назад
Динамическое программирование: не так страшен чёрт...
Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS. Часто встречаю в интернете такое: «Мне дали на 4-м туре собеседования в Яндексе задачу динамического программирования — уууу — какая сложная была!», «Сейчас крупнейшие зарубежные компании на собеседовании сразу дают динамику, чтобы отсеять слабых программистов». Из-за устоявшихся стереотипов такие задачи считаются очень сложными. Предполагается, что решение их подвластно немногим. Что же это за...
4 года назад
Разбор задачи "Сумма степеней двойки". Тема: динамическое программирование
Ещё одна интересная задача. Поначалу она может показаться чисто математической, но суть решения кроется совсем не в этом :) Собственно, задание: Любое натуральное число можно представить в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2. Суммы, различающиеся лишь порядком слагаемых, считаются одинаковыми. Например, для числа 7 таких представлений 6 (4+2+1, 4+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1). Требуется написать программу, которая найдет количество способов такого представления заданного числа N...