Контест Junior Динамическое программирование спрашивают часто обновлено
Подъём по лестнице с минимальной платой
Условие
Лестница из n ступенек, за вставание на ступеньку i нужно заплатить cᵢ. Вы стоите на земле (ступенька 0, бесплатно) и за один шаг поднимаетесь на 1 или на 2 ступеньки. Нужно оказаться на последней ступеньке n (её цена тоже платится). Найдите минимальную плату.
Ввод: в первой строке n (1 ≤ n ≤ 2500), во второй n чисел c₁ … cₙ (0 ≤ cᵢ ≤ 10⁴).
Вывод: минимальная плата.
Пример 1
Ввод:
4
1 100 1 5
Вывод:
7
Пример 2
Ввод:
1
7
Вывод:
7
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Предыдущий вопрос
Наибольшая возрастающая подпоследовательность за n log n
Следующий вопрос
Торговля акцией с комиссией и днём перерыва