Хорошая задача на динамическое программирование, без каких-либо подводных камней. Читаем условие:
Как часто бывает в задачах на динамическое программирование, основная сложность заключается в придумывании рекуррентного соотношения и понимании принципа работы, а не в написании кода (потому что обычно в них один или два цикла, просто заполняющие массив). Поэтому давайте сконцентрируемся на методе решения.
Для начала надо определить, что будет состоянием в динамике. В данной задаче с этим нет проблем - это номер платформы, на которой стоит герой. Для каждого возможного состояния мы будем считать минимальную количество энергии, которое надо потратить, чтобы в нём оказаться.
Чтобы посчитать ответ для состояния i, надо рассмотреть все переходы, откуда мы могли в него придти:
- из состояния i - 1, тогда затраченная энергия будет равна ответу для состояния i - 1 плюс модуль разности высот между платформами i и i - 1,
- из состояния i - 2, в этом случае затраченная энергия будет равна ответу для состояния i - 2 плюс утроенный модуль разности высот между платформами i и i - 2.
И среди всех этих возможностей надо выбрать оптимальный переход, то есть с минимальными затратами энергии.
Давайте реализуем это решение. Сначала считаем входные данные:
Заметим, что количество платформ однозначно можно получить из длины списка, поэтому это значение можно не хранить. Заведём массив, где для каждого состояния будем хранить ответ (минимальное количество энергии, необходимое, чтобы попасть в него). А также отдельно обработаем случай второй платформы (так как в это состояние существует только один переход, а не два, как во все остальных):
Теперь пройдёмся в цикле по всем остальным состояниям (платформам) и посчитаем ответы как минимум из двух возможных переходов. По сути, здесь лишь запись того, что мы описали текстом:
Осталось вывести ответ. В нашем случае он будет храниться в последнем элементе массива res, так как он соответствует последнему состоянию динамики, то есть нахождению на последней платформе:
Предыдущий выпуск: Задача 27. Художник
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
