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
Problem: Frog 2
Problem Link: https://atcoder.jp/contests/dp/tasks/dp_b
Approach:
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.
We need to check all possible combinations within K distance. That's why we need Dynamic Programming.
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.
We can calculate the cost required to move from position k to position i using, dp[i-k] + abs(stones[i-k] - stones[i]))
Now for each amount jump of size 0 to K, we can take the minimum among costs using the previous equation.
From each i starting from 0 to N, we can calculate the optimal cost acquired using the previous formula.
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]);
}