Question Link : https://www.codingninjas.com/studio/problems/frog-jump_3621012?leftPanelTab=0

Using Recursive DP :

1. The function rec is a recursive function that calculates the minimum cost of reaching the index position in the heights vector.

2. The dp vector is used to store the minimum cost at each position. The initial values of the dp vector are set to -1, indicating that they haven't been calculated yet.

3. If the minimum cost for the index position has already been calculated (i.e., dp[index] != -1), it is directly returned.

4. 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])).

5. The minimum cost between x and y is calculated using the min function and stored in dp[index]. This value is also returned.

6. The frogJump function initializes the dp vector with size n and calls the rec function with n-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 the heights 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);
}

Using Iterative DP:

1. The rec function iterates through the positions of the heights vector starting from index i and calculates the minimum cost to reach each position.

2. Inside the loop, two variables x and y are initialized. x represents the cost of jumping from the previous position to the current position, and y represents the cost of jumping from two positions back to the current position.

3. The minimum cost between x and y is calculated using the min function and stored in the dp vector at the current position.

4. By continuously updating the dp vector in each iteration, the loop calculates the minimum cost for each position, moving from left to right.

5. The frogJump function initializes the dp vector with size n and sets the first position's cost to 0 (since the frog is already at the first position).

6. It then calls the rec function starting from the second position (rec(1, dp, heights)), which fills in the dp vector with the minimum costs for each position.

7. 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];
}

Space Optimization :

1. The rec function iterates through the positions of the heights vector starting from index i and calculates the minimum cost to reach each position.

2. Inside the loop, three variables are used: prev, prev2, and curr. prev represents the minimum cost of the previous position, prev2 represents the minimum cost of two positions back, and curr represents the current minimum cost.

3. The minimum cost x of jumping from the previous position to the current position is calculated by adding prev with the absolute difference between the current and previous heights.

4. 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 adding prev2 with the absolute difference between the current and two positions back heights.

5. The minimum cost between x and y is stored in curr.

6. In each iteration, the values of prev2 and prev are updated. prev2 is assigned the value of prev, and prev is assigned the value of curr.

7. After the loop finishes, the final minimum cost to reach the last position is stored in prev.

8. The frogJump function calls the rec 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);
}