Запрограммировать задачу, которую решил через рисунок
Задача
Компьютерная игра
Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю, у героя уходит |y2-y1| единиц энергии, где y1 и y2 – высоты, на которых расположены эти платформы. Кроме того, у героя есть супер прием, который позволяет перескочить через платформу, но на это затрачивается 3 * |y3-y1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.
Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней?
Входные данные
В первой строке входного файла INPUT.TXT записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 – высоты, на которых располагаются платформы.
Выходные данные
В выходной файл OUTPUT.TXT запишите единственное число – минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же в предположении, что cheat-коды использовать нельзя).
Моё визуальное решение:
Допустим на вход поступило число 4 и цифры 1 10 14 3. Тогда мы можем визуализировать это в виде рисунка:
Над стрелочками написано количество затраченной энергии, чтобы добраться до этой платформы
Проблема:
Я понимаю, что это определенно решается через рекурсию. Пробовал просчитать все варианты через рекурсию и найти минимальное значение из всех вариантов. Большая просьба, если это возможно, решить задачу, опираясь на мой рисунок. Если решали через известный алгоритм, то скажите его название в решении!
Рекурсия не единственный, и даже, наверное, не самый простой способ решать задачи методом динамического программирования.
Составим таблицу, в каждую ячейку которой будем записывать минимально возможную энергию, для достижения соответствующей платформы.
На первой платформе мы стоим изначельно, энергия для ее достижения не требуется
1101430
До второй платформы можем добраться единственным способом – с первой платформы. Тратим 9 энергии на прыжок, плюс к тому значению, что требовалось для достижения первой платформы (т.е. 0)
11014309
До третьей можно добраться двумя способами. С первой (0 + |14 - 1| * 3) или со второй – (9 + |14 - 10|). Второй вариант дешевле
1101430913
Так же и для 4 и всех последующих шагов, зная самые дешевые решения для предыдущих, проверяем что дешевле – прыгнуть или перепрыгнуть.
110143091324
Итого, для решения задачи можно составить массив для всех предыдущих шагов, и пользоваться им для последующих, но для этой задачи достаточно будет хранить всего два предыдущих значения.