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
Problem: Frog Jump
Problem Link: https://www.codingninjas.com/codestudio/problems/frog-jump_3621012
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;
}