Daily Dose of DSA - Day 19
Frog jump using Rec DP(Top-Down Approach)(TC : O(n) & SC : O(n + n (call stack))& Itr DP( Bottom-up Approach)(TC : O(n) & SC : O(n)(O(1) in Sp.Optim))
Table of contents
Question Link : https://www.codingninjas.com/studio/problems/frog-jump_3621012?leftPanelTab=0
PermalinkUsing Recursive DP :
The function
rec
is a recursive function that calculates the minimum cost of reaching theindex
position in theheights
vector.The
dp
vector is used to store the minimum cost at each position. The initial values of thedp
vector are set to -1, indicating that they haven't been calculated yet.If the minimum cost for the
index
position has already been calculated (i.e.,dp[index] != -1
), it is directly returned.Otherwise, two possibilities are considered: a. Jumping from the previous position to the current position (
x = rec(index-1, dp, heights) + abs(heights[index] - heights[index-1])
). b. Jumping from two positions back to the current position (y = rec(index-2, dp, heights) + abs(heights[index] - heights[index-2])
).The minimum cost between
x
andy
is calculated using themin
function and stored indp[index]
. This value is also returned.The
frogJump
function initializes thedp
vector with sizen
and calls therec
function withn-1
as the starting index. It returns the minimum cost to reach the last position (dp[n-1]
). the code finds the minimum cost of jumping from one position to another in theheights
vector, considering that the frog can jump one or two positions at a time. The dynamic programming approach is used to avoid redundant calculations by storing and reusing the minimum costs.
#include <bits/stdc++.h>
int rec(int index,vector<int>&dp,vector<int>&heights)
{
if(index==0) return 0;
if(dp[index]!=-1) return dp[index];
int x = rec(index-1,dp,heights)+abs(heights[index]-heights[index-1]);
int y = INT_MAX;
if(index>1)
y = rec(index-2,dp,heights)+abs(heights[index]-heights[index-2]);
return dp[index]=min(x,y);
}
int frogJump(int n, vector<int> &heights)
{
vector<int>dp(n,-1);
return rec(n-1,dp,heights);
}
PermalinkUsing Iterative DP:
The
rec
function iterates through the positions of theheights
vector starting from indexi
and calculates the minimum cost to reach each position.Inside the loop, two variables
x
andy
are initialized.x
represents the cost of jumping from the previous position to the current position, andy
represents the cost of jumping from two positions back to the current position.The minimum cost between
x
andy
is calculated using themin
function and stored in thedp
vector at the current position.By continuously updating the
dp
vector in each iteration, the loop calculates the minimum cost for each position, moving from left to right.The
frogJump
function initializes thedp
vector with sizen
and sets the first position's cost to 0 (since the frog is already at the first position).It then calls the
rec
function starting from the second position (rec(1, dp, heights)
), which fills in thedp
vector with the minimum costs for each position.Finally, the function returns the minimum cost to reach the last position, which is stored in
dp[n-1]
.
In simple terms, the code uses a loop to calculate the minimum cost for each position in the heights
vector. It considers two possibilities: jumping from the previous position or jumping from two positions back. By continuously updating the dp
vector, it finds the minimum cost for each position, starting from the second position. The final result is the minimum cost to reach the last position.
#include <bits/stdc++.h>
void rec(int i,vector<int>&dp,vector<int>&heights)
{
int n = (int)heights.size();
for(i;i<n;i++)
{
int x,y=INT_MAX;
x = dp[i-1] + abs(heights[i]-heights[i-1]);
if(i>1)
{
y = dp[i-2] + abs(heights[i]-heights[i-2]);
}
dp[i] = min(x,y);
}
}
int frogJump(int n, vector<int> &heights)
{
vector<int>dp(n,0);
dp[0]=0;
rec(1,dp,heights);
return dp[n-1];
}
PermalinkSpace Optimization :
The
rec
function iterates through the positions of theheights
vector starting from indexi
and calculates the minimum cost to reach each position.Inside the loop, three variables are used:
prev
,prev2
, andcurr
.prev
represents the minimum cost of the previous position,prev2
represents the minimum cost of two positions back, andcurr
represents the current minimum cost.The minimum cost
x
of jumping from the previous position to the current position is calculated by addingprev
with the absolute difference between the current and previous heights.If the current position is greater than index 1, the minimum cost
y
of jumping from two positions back to the current position is calculated by addingprev2
with the absolute difference between the current and two positions back heights.The minimum cost between
x
andy
is stored incurr
.In each iteration, the values of
prev2
andprev
are updated.prev2
is assigned the value ofprev
, andprev
is assigned the value ofcurr
.After the loop finishes, the final minimum cost to reach the last position is stored in
prev
.The
frogJump
function calls therec
function starting from the second position (rec(1, heights)
), and it returns the final minimum cost.
In simple terms, the code uses a loop to calculate the minimum cost for each position in the heights
vector. It keeps track of the minimum costs of the previous position and two positions back. By iteratively updating these values, it finds the minimum cost to reach the last position. The final result is returned as the minimum cost for the frog to jump from the second position to the last position.
#include <bits/stdc++.h>
int rec(int i,vector<int>&heights)
{
int n = (int)heights.size();
int prev = 0;
int prev2 = 0;
for( i;i<n;i++)
{
int x,y=INT_MAX;
x = prev + abs(heights[i]-heights[i-1]);
if(i>1)
{
y = prev2 + abs(heights[i]-heights[i-2]);
}
int curr = min(x,y);
prev2 = prev;
prev = curr;
}
return prev;
}
int frogJump(int n, vector<int> &heights)
{
return rec(1,heights);
}