hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Frog 2


  • Approach:

    1. At the very first look, it will seem to be like, a Greedy Problem. Just the selection of stones within K distance with the absolute height difference may give the optimal result. However, it will not.

    2. We need to check all possible combinations within K distance. That's why we need Dynamic Programming.

    3. For DP[i], we need to find out the minimum cost that can be acquired while moving to i'th position from any of the prior i-1, i-2, i-3, .... , (i-k)'th position.

    4. We can calculate the cost required to move from position k to position i using, dp[i-k] + abs(stones[i-k] - stones[i]))

    5. Now for each amount jump of size 0 to K, we can take the minimum among costs using the previous equation.

    6. From each i starting from 0 to N, we can calculate the optimal cost acquired using the previous formula.

    7. Later we will return dp[N-1]


  • Time and Space Complexity:

    • Time Complexity: O(N*K)

    • Space Complexity: O(N)


Code [C++]

#include <bits/stdc++.h>


using namespace std;


int main(){

int n, k;

long long x;

scanf("%d %d", &n, &k);

vector<long long int>stones;

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

scanf("%lld", &x);

stones.push_back(x);

}

vector<long long int>dp(n+2);

dp[0] = 0;

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

long long int ret = INT_MAX;

for(int j=1; j<=k; j++){

if((i-j)<0) break;

ret = min(ret, dp[i-j] + abs(stones[i-j] - stones[i]));

}

dp[i] = ret;

}

printf("%lld\n", dp[n-1]);

}