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

Обозначим через dp₁(i) наибольшее количество очков при приземлении на ступеньку i прыжком на одну ступеньку, а через dp₂(i) — прыжком на две.

Переходы: dp₁(i) = aᵢ + max(dp₁(i−1), dp₂(i−1)); dp₂(i) = aᵢ + dp₁(i−2), поскольку два прыжка на две ступеньки подряд запрещены.

Для чисел 5, −4, 6, 3, −7, 8, 2, 4 получаем на 8-й ступеньке: dp₁(8) = 28, dp₂(8) = 19. Один из оптимальных маршрутов: на ступеньки 1, 3, 4, 6, 7, 8. Сумма: 5 + 6 + 3 + 8 + 2 + 4 = 28.

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