Frog 2

So here I'm going to solve a AtCoder problem from the AtCoder Educational Contest
Problem Statement : https://atcoder.jp/contests/dp/tasks/dp_b

When you got the idea of Frog 1. Frog 2 is trivial : do one more for loop.

Time complexity : O(n^2)
Space complexity : O(n)

This question again is a very trivial dp problem.

C++ code :

#include <iostream>

#include <climits>

#include <vector>

using namespace std;

int main(){

ios::sync_with_stdio(0);

cin.tie(0);

int n,K;

cin >> n >> K;

vector<int> v(n+3),ret(n+3,INT_MAX);

for (int i=0; i<n; ++i) cin >> v[i];

ret[0]=0;

for (int i=0; i<n; ++i){

for (int k=1; k<=K; ++k) ret[i+k] = min(ret[i+k],abs(v[i]-v[i+k])+ret[i]);

}

cout << ret[n-1];

return 0;

}