Лестница с призами. Робот начинает с 0 очков и должен закончить движение на последней ступеньке. За один прыжок он поднимается на одну или две ступеньки, но два прыжка на две ступеньки подряд запрещены. Числа на ступеньках снизу вверх: 5, −4, 6, 3, −7, 8, 2, 4. Помогите роботу набрать как можно больше очков.

Обозначим через A_i наибольшее число очков при попадании на ступеньку i прыжком на одну ступеньку, а через B_i — прыжком на две ступеньки.

Прыжок на одну ступеньку может следовать за любым допустимым прыжком: A_i = max(A_i−1, B_i−1) + число на ступеньке i. Прыжок на две ступеньки может следовать только за прыжком на одну: B_i = A_i−2 + число на ступеньке i.

Для этих чисел лучшие результаты на ступеньках 1–8: 5, 1, 11, 14, 7, 22, 24, 28. Например, путь, дающий 28 очков: на ступеньки 1, 3, 4, 6, 7 и 8. Два прыжка на две ступеньки подряд здесь не используются.

Ответ: 28 очков.