Рассмотрим простую задачу на динамическое программирование, в которой построение ответа почти в два раза больше, чем само решение. Читаем условие:
Задача не является продолжением или вариацией задачи 16. Лесенка, но решать будем тоже с помощью динамики. Считаем входные данные и сразу преобразуем их к числовым типам:
Состоянием в динамическом программировании будет номер ступеньки, на которой стоит Вова. Чтобы узнать переходы, надо ответить на вопрос "Как Вова мог здесь оказаться?". Ответ очень простой - или с предыдущей ступеньки или через одну от неё. И надо лишь выбрать максимум среди этих двух чисел.
Ступеньки нумеруются с первой, поэтому можем добавить фиктивную - нулевую - на которой Вова стоит изначально. Тогда база динамики будет 0.
Здесь мы, помимо базы, инициализировали массив ещё парой значений, чтобы не переживать из-за выхода за границы массива в основном цикле. Это стало возможно в том числе благодаря тому, что входной массив содержит не меньше двух элементов.
После этого цикла в массиве dp будет находиться максимальная сумма, которую Вова сможет набрать, дойдя до каждой из ступенек.
Вторая часть этой задачи - это построение маршрута. Как обычно в динамическом программировании, будем строить его с конца:
Начинаем с последней ступеньки. А потом проверяем равенство, чтобы убедиться, что Вова пришёл с предыдущей ступеньки. Если это не так, значит он её перепрыгнул. Повторяем так до тех пор, пока не дойдём до нулевой ступеньки.
Вывод ответа здесь тоже немного интереснее - массив надо развернуть и удалить нулевую ступеньку. Это можно сделать одним слайсом.
Таким образом мы получили линейное по времени и памяти решение.
Предыдущий выпуск: Задача 899. Баланс скобок
Задонатить автору на бусти.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
