1. Идея

Нужно найти минимальную суммарную стоимость пути лягушки от первого камня до последнего.

У лягушки есть только два варианта перехода на камень i:

• прийти с камня i-1
• прийти с камня i-2

Это сразу подсказывает динамическое программирование.

Обозначим dp[i] — минимальное усилие, нужное, чтобы попасть на камень i.

Тогда:

• если лягушка прыгает с i-1, стоимость будет dp[i-1] + abs(h[i] - h[i-1])
• если с i-2, стоимость будет dp[i-2] + abs(h[i] - h[i-2])

Берём минимум из этих двух вариантов.

Но хранить весь массив dp не обязательно: для вычисления очередного значения нужны только два предыдущих.

2. Наблюдения

Наблюдение 1

На первый камень лягушка уже стоит, значит:

• dp[0] = 0

Наблюдение 2

На второй камень можно попасть только с первого:

• dp[1] = abs(h[1] - h[0])

Наблюдение 3

Для любого i >= 2 других способов попасть на камень i, кроме как с i-1 или i-2, нет. Поэтому переход выглядит так:

• dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]))

Наблюдение 4

Так как в формуле используются только dp[i-1] и dp[i-2], достаточно хранить две переменные:

• prev2 — значение для dp[i-2]
• prev1 — значение для dp[i-1]

Это уменьшает расход памяти до O(1).

3. Алгоритм

1. Считать n и массив высот h.
2. Если n == 1, ответ равен 0.
3. Инициализировать:
   • prev2 = 0
   • prev1 = abs(h[1] - h[0])
4. Для каждого i от 2 до n-1:
   • посчитать стоимость прыжка с предыдущего камня:
     • cost1 = prev1 + abs(h[i] - h[i-1])
   • посчитать стоимость прыжка через один камень:
     • cost2 = prev2 + abs(h[i] - h[i-2])
   • взять минимум:
     • cur = min(cost1, cost2)
   • сдвинуть значения:
     • prev2 = prev1
     • prev1 = cur
5. Вывести prev1.

4. Почему это работает

Докажем, что алгоритм действительно находит минимальное суммарное усилие.

Рассмотрим любой камень i.

Лягушка может попасть на него только двумя способами:

• с камня i-1
• с камня i-2

Других допустимых прыжков по условию нет.

Если последний прыжок был с камня i-1, то общая стоимость пути равна:

• минимальная стоимость добраться до i-1
• плюс стоимость прыжка abs(h[i] - h[i-1])

То есть это dp[i-1] + abs(h[i] - h[i-1]).

Если последний прыжок был с камня i-2, то стоимость равна:

• dp[i-2] + abs(h[i] - h[i-2])

Чтобы получить минимальную стоимость для камня i, нужно выбрать лучший из этих двух вариантов:

• dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]))

База тоже верна:

• dp[0] = 0, потому что старт уже на первом камне
• dp[1] = abs(h[1] - h[0]), потому что на второй камень можно попасть только напрямую с первого

Значит, по индукции все значения вычисляются правильно, и итоговый ответ для последнего камня тоже правильный.

Почему можно хранить только две переменные? Потому что для вычисления текущего значения нужны только два предыдущих. Следовательно, массив dp не обязателен.

5. Сложность

• Время: O(n), потому что каждый камень обрабатывается один раз.
• Память: O(1), не считая массива высот, потому что дополнительно используются только несколько переменных.

6. Код на C++17

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    if (n == 1) {
        cout << 0 << "\n";
        return 0;
    }

    long long prev2 = 0;
    long long prev1 = llabs(h[1] - h[0]);

    for (int i = 2; i < n; i++) {
        long long cost1 = prev1 + llabs(h[i] - h[i - 1]);
        long long cost2 = prev2 + llabs(h[i] - h[i - 2]);
        long long cur = min(cost1, cost2);
        prev2 = prev1;
        prev1 = cur;
    }

    cout << prev1 << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
h = list(map(int, input().split()))

if n == 1:
    print(0)
else:
    prev2 = 0
    prev1 = abs(h[1] - h[0])

    for i in range(2, n):
        cost1 = prev1 + abs(h[i] - h[i - 1])
        cost2 = prev2 + abs(h[i] - h[i - 2])
        cur = min(cost1, cost2)
        prev2 = prev1
        prev1 = cur

    print(prev1)