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

Обозначим через dp₁(i) наибольшее количество очков при приземлении на ступеньку i прыжком на одну ступеньку, а через dp₂(i) — прыжком на две. Тогда dp₁(i) = aᵢ + max(dp₁(i−1), dp₂(i−1)), а dp₂(i) = aᵢ + dp₁(i−2).

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

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