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 Jump


  • 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 2 distances. 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 the prior (i-1)th, (i-2)th position.

    • We can calculate the cost required to move from position i-2 to position i using, dp[i-2] + abs(stones[i-2] - stones[i])) and from i -1 to position i using, dp[i-1] + abs(stones[i-1] - stones[i])).

    • Now we need to take the minimum among costs using two previous calculations.

    • 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]


  • Space Optimization Technique:

    • If you carefully see, at each step, we are only working with 2 previous positions with respect to i.

    • So instead of using the whole DP array, we can use 2 variables to store 2 previous values.


  • Time and Space Complexity ( Most Optimized Solution ):

    • Time Complexity: O(N)

    • Space Complexity: O(1)


Code [C++] (Recursion With Dynamic Programming )

#include <bits/stdc++.h>


using namespace std;


int solve(int pos, vector<int> & height, vector<int> & dp){

if(pos <= 1) return abs(height[pos] - height[0]);

if(dp[pos] != -1) return dp[pos];

int ans = min(solve(pos-1, height, dp) + abs(height[pos-1] - height[pos]),

solve(pos-2, height, dp) + abs(height[pos-2] - height[pos]));

return (dp[pos] = ans);

}


int frogJump(int n, vector<int> &heights)

{

vector<int>dp(n+1, -1);

return solve(n-1, heights, dp);

}

Code [C++] (Iterative Dynamic Programming)

#include <bits/stdc++.h>


int frogJump(int n, vector<int> &height)

{

vector<int>dp(n+1, -1);

dp[0] = 0, dp[1] = abs(height[0] - height[1]);

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

dp[i] = min(dp[i-1]+abs(height[i]-height[i-1]),

dp[i-2] + abs(height[i] - height[i-2]));

}

return dp[n-1];

}

Code [C++] (Dynamic Programming With Space Otimization)

#include <bits/stdc++.h>


int frogJump(int n, vector<int> &height)

{

int first = 0, second = abs(height[0] - height[1]), third;

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

third = min(second+abs(height[i]-height[i-1]),

first + abs(height[i] - height[i-2]));

first = second;

second = third;

}

return third;

}