В технике, экономике и некоторых других направлениях иногда приходится решать задачи на поиск оптимального пути или состояния. По сути это цель любой автоматизации - минимизировать затраты или получить наилучший результат. Это понятие ввёл в 40-ых годах прошлого века Ричард Беллман. Идея достаточно простая - для того чтобы получить конечный результат, необходимо предварительно решить несколько вспомогательных задач. Решить каждую из которых можно решив их предварительные задачи. Саму постановку...

Представьте, что вы стоите у подножия высокой лестницы и хотите узнать, сколькими способами можно подняться на сотую ступеньку, если за один шаг можно преодолеть либо одну, либо две ступени. Можно ли сразу дать ответ? Конечно, нет — задача кажется необъятной. Но что, если начать с малого: сначала посчитать способы для первой ступеньки, потом для второй, третьей… и так постепенно добраться до сотой? Именно в этом и заключается суть динамического программирования. В задании 23 ЕГЭ по информатике проверяется умение анализировать работу алгоритма с ветвлениями и циклами...