Frog 1

Solution by dudu — 100 pts

Code / Notes

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> H;
vector<int> memo;

int custoProFinal(int i) {
    if (i == N-1) return 0;
    if (i == N-2) return abs(H[i+1]-H[i]);
    if (memo[i] != -1) return memo[i];

    int opt1 = abs(H[i+1]-H[i]) + custoProFinal(i+1);
    int opt2 = abs(H[i+2]-H[i]) + custoProFinal(i+2);
    memo[i] = min(opt1, opt2);
    return memo[i];
}

int main() {
    cin >> N;
    H = vector<int>(N);
    for (auto &x : H) cin >> x;

    memo = vector<int>(N,-1);
    cout << custoProFinal(0) << endl;
}

Last updated 1 month, 1 week ago

« Back to problem