(MCCME) Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму (положительное целое число). Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки. На последнюю ступеньку наступать обязательно. Ввести стоимость ступенек через запятую, вывести минимальную сумму прохода.
- Пояснения и алгоритм — в полном тексте задачи
1,3,1,1,2,2
- Идеи
- Проход на первую и на вторую ступеньки равен их стоимости
На i-ю ступеньку мальчик мог попасть только с (i-1)-й или с (i-2)-й ступенек. Предположим, мы уже знаем минимальную сумму прохода на две предыдущие ступеньки. Тогда минимальная сумма прохода на i-ю ступеньку — это меньшая из этих сумм + стоимость самой ступеньки, и никак иначе!
- Формализация на русском:
- Запомним стоимость прохода на 0-ю и 1-ю ступеньки (для второй ступеньки они и есть «пред-предыдущая» и «предыдущая»)
- По каждой ступеньке, начиная со второй:
Вычислим проход на очередную ступеньку как её собственную стоимость, плюс минимум из стоимостей проходов на пред-предыдущую и предыдущую ступеньки
На следующем шаге предыдущая ступенька будет пред-предыдущей,
…а текущая — предыдущей
- На последнем шаге мы вычислили минимальную стоимость прохода на последнюю ступеньку — это и есть ответ
5