Frog 1 – Atcoder DP

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 1e5;

int h[MAX_N];
int memo[MAX_N];

int dp(int i) {
    if (i == 0) {
        return 0;
    }

    if (i == 1) {
        return abs(h[1] - h[0]);
    }

    if (memo[i] != -1) {
        return memo[i];
    }

    memo[i] = min(dp(i - 1) + abs(h[i] - h[i - 1]), dp(i - 2) + abs(h[i] - h[i - 2]));
    return memo[i];
}

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

    memset(memo, -1, sizeof(memo));

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

    cout << dp(n - 1);

    return 0;
}