Untitled

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
603 B
1
Indexable
Never
#include <iostream>
using namespace std;
const int maxn = 100005;
int n, k;
int niza[maxn];
int memo[maxn];
int f(int x) {
    if(x == n - 1) {
        return 0;
    }
    if(memo[x] != -1) {
        return memo[x];
    }
    int najmal = 2e9;
    for(int i = 1; i <= k; i++) {
        if(x + i < n) {
            najmal = min(najmal, f(x + i) + abs(niza[x] - niza[x + i]));
        }
    }
    memo[x] = najmal;
    return memo[x];
}
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> niza[i];
        memo[i] = -1;
    }
    cout << f(0) << endl;
    return 0;
}

// 2504