Предлагаю потренироваться решать задачи на динамическое программирование на одной из классических задач. Читаем условие: Как определить, что задача на динамическое программирование? Кроме того, что на сайте указан раздел, из которого задача, метод динамического программирования чаще всего помогает отвечать на вопросы "сколько способов?" и "какой способ оптимальный?". Да, есть ещё варианты, например, зная количество способов и первое число в "решении" можно найти k-ое по счёту решение. Итак, в этой задаче как раз надо посчитать количество способов подняться на лестницу...

Хорошая задача на динамическое программирование, без каких-либо подводных камней. Читаем условие: Как часто бывает в задачах на динамическое программирование, основная сложность заключается в придумывании рекуррентного соотношения и понимании принципа работы, а не в написании кода (потому что обычно в них один или два цикла, просто заполняющие массив). Поэтому давайте сконцентрируемся на методе решения. Для начала надо определить, что будет состоянием в динамике. В данной задаче с этим нет проблем - это номер платформы, на которой стоит герой...

Очень классная задача на динамическое программирование, в которой надо ещё придумать, как быстро посчитать результат. Читаем условие: Идея динамического программирования лежит на поверхности - чтобы вычислить стоимость для N надо знать стоимость для S и N - S (и правильно распределить, к чему прибавить 1, а к чему - 2). Получаем одномерную динамику - ответ зависит лишь от количества элементов в множестве. База динамики: для 1 ответ 0. Если загаданное число среди одного, то не надо задавать вопросов, чтобы узнать, что это за число...

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