Frog jump with K distances

Why greedy approach will not work:

As the problem states to find the minimum energy required, the first approache that comes to our mind is greedy.

In greedy we tend to make our moves greedily on each step, here the greedy move will be to select the path with minimum energy. But this approach will fail here as total energy required by the frog depends upon the path taken by the frog. If the frog just takes the minimum energy path in every stage it can happen that it eventually takes a path with greater energy after a certain number of jumps.

The problem here is asking for the minimum possible energy and as discussed in the previous problem, this kind of problem can be solved using recusion.

Using the steps described in previous problem, write the recursive solution:

Express the problem in terms of indexes: This can be easily done as there are array indexes [0,1,2,..., n-1]. As f(n-1) signifies the minimum amount of energy required to move from stair 0 to stair n-1. Therefore f(0) simply should give us the answer as 0(base case).

Try all the choices to reach the goal: As the frog can make jump upto K steps. Therefore, we can set a for loop to run from 1 to K, and in each iteration, a function call will be made, corresponding to a step.

Take the minimum of all the choices: As the problem statement asks to find the minimum total energy, return the minimum of all K choices. Also if the index is less than the number of steps, we can’t try the all that step.

/*It is pseudocode and not tied to 
any specific programming language.*/
f(ind, height){
    if(ind == 0) return 0
    mmSteps = INT_MAX
    for(int j = 1; j <= K; j++){
        if((ind-j) >= 0){
            jump = f(ind-j), height) + abs(a[ind] - a[ind-j]);
            mmSteps = min(mmSteps, jump);
        }
    }
    return mmSteps;
}

Base case: When N = 0, then we will have only one option to stay at the same place and that would take 0 energy.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    //Helper function for recursion
    int func(int ind, vector<int> &heights, int k){
        //Base case
        if(ind == 0){
            return 0;
        }
        //Initialize mmStep to INT_MAX
        int mmStep = INT_MAX;
        
        //Try all possible steps
        for(int j = 1; j <= k; j++){
            
            //Check if ind-j is non negative 
            if(ind-j >= 0){
                int jump = func(ind-j, heights, k) + abs(heights[ind] - heights[ind-j]);
                
                //Update the mimimum energy
                mmStep = min(jump, mmStep);
            }
        }
        //Return the answer
        return mmStep;
    }
public:
    /* Function to find the mimimum 
    energy to reach last stair*/
    int frogJump(vector<int> &heights, int k) {
        int ind = heights.size()-1;
        
        //Return the mimimum energy
        return func(ind, heights, k);
    }
};

int main() {
    vector<int> height{15, 4, 1, 14, 15};
    int k = 3;
    
    // Create an instance of Solution class
    Solution sol;

    // Print the answer
    cout << "Minimum energy : " << sol.frogJump(height, k) << endl;

    return 0;
}
import java.util.*;

class Solution {
    //Helper function for recursion
    private int func(int ind, int[] heights, int k) {
        //Base case
        if (ind == 0) {
            return 0;
        }
        //Initialize mmStep to INT_MAX
        int mmStep = Integer.MAX_VALUE;
        
        //Try all possible steps
        for (int j = 1; j <= k; j++) {
            
            //Check if ind-j is non negative
            if (ind - j >= 0) {
                int jump = func(ind - j, heights, k) + Math.abs(heights[ind] - heights[ind - j]);
                
                //Update the mimimum energy
                mmStep = Math.min(jump, mmStep);
            }
        }
        //Return the answer
        return mmStep;
    }
    /* Function to find the mimimum 
    energy to reach last stair*/
    public int frogJump(int[] heights, int k) {
        int ind = heights.length - 1;
        
        //Return the mimimum energy
        return func(ind, heights, k);
    }
    
    public static void main(String[] args) {
        int[] heights = {15, 4, 1, 14, 15};
        int k = 3;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Print the answer
        System.out.println("Minimum energy: " + sol.frogJump(heights, k));
    }
}
class Solution:
    #Helper function for recursion
    def func(self, ind, heights, k):
        #Base case
        if ind == 0:
            return 0
        
        #Initialize mmStep to INT_MAX
        mmStep = float('inf')
        
        #Try all possible steps
        for j in range(1, k + 1):
            
            #Check if ind-j is non negative
            if ind - j >= 0:
                jump = self.func(ind - j, heights, k) + abs(heights[ind] - heights[ind - j])
                
                #Update the mimimum energy
                mmStep = min(mmStep, jump)
                
        #Return the answer
        return mmStep
    
    """Function to find the mimimum 
    energy to reach last stair"""
    def frogJump(self, heights, k):
        ind = len(heights) - 1
        
        #Return the mimimum energy
        return self.func(ind, heights, k)
    
if __name__ == "__main__":
    heights = [15, 4, 1, 14, 15]
    k = 3
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the answer
    print("Minimum energy:", sol.frogJump(heights, k))
class Solution {
    //Helper function for recursion
    func(ind, heights, k) {
        //Base case
        if (ind === 0) {
            return 0;
        }
        
        //Initialize mmStep to INT_MAX
        let mmStep = Infinity;
        
        //Try all possible steps
        for (let j = 1; j <= k; j++) {
            
            //Check if ind-j is non negative
            if (ind - j >= 0) {
                let jump = this.func(ind - j, heights, k) + Math.abs(heights[ind] - heights[ind - j]);
                
                //Update the mimimum energy
                mmStep = Math.min(jump, mmStep);
            }
        }
        //Return the answer
        return mmStep;
    }
    
    /* Function to find the mimimum 
    energy to reach last stair*/
    frogJump(heights, k) {
        let ind = heights.length - 1;
        
        //Return the mimimum energy
        return this.func(ind, heights, k);
    }
}

    let heights = [15, 4, 1, 14, 15];
    let k = 3;
    
    // Create an instance of Solution class
    let sol = new Solution();
    
    // Print the answer
    console.log("Minimum energy:", sol.frogJump(heights, k));

Complexity Analysis:

Time Complexity: O(k^N),The function is called recursively for each index from N-1 down to 0, where N is the length of the heights array.

Space Complexity:The space complexity of this recursive approach is O(N). This is because the maximum depth of the recursion stack can go up to n, due to the linear nature of the stack usage relative to the input size n.

Memoization tends to store the value of subproblems in some map/ table. As, here we have only one parameter in recursive function, so we can create an 1D array to store the values of subproblems.

Steps to convert Recursive code to memoization solution:

Declare an Array dp[] of Size n: Here, n is the parameter or size of the problem, as the highest number of subproblems can be n(including 0 as well). It represents the solution to the subproblem for any given index. Initially, fill the array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.

Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to recursion with memoization
    int func(int ind, vector<int> &heights, int k, vector<int>& dp){
        //Base case
        if(ind == 0){
            return 0;
        }
        
        /* If the result for this index has 
        been previously calculated, return it */
        if (dp[ind] != -1) return dp[ind];
        
        //Initialize mmStep to INT_MAX
        int mmStep = INT_MAX;
        
        //Try all possible steps
        for(int j = 1; j <= k; j++){
            
            //Check if ind-j is non negative 
            if(ind-j >= 0){
                int jump = func(ind-j, heights, k, dp) + abs(heights[ind] - heights[ind-j]);
                
                //Update the mimimum energy
                mmStep = min(jump, mmStep);
            }
        }
        //Return the answer
        return dp[ind] = mmStep;
    }
public:
    /* Function to find the mimimum 
    energy to reach last stair*/
    int frogJump(vector<int> &heights, int k) {
        int ind = heights.size()-1;
        
        /*Initialize a memoization array
        to store calculated results*/
        vector<int> dp(ind+1, -1); 
        
        //Return the mimimum energy
        return func(ind, heights, k, dp);
    }
};

int main() {
    vector<int> height{15, 4, 1, 14, 15};
    int k = 3;
    
    // Create an instance of Solution class
    Solution sol;

    // Print the answer
    cout << "Minimum energy : " << sol.frogJump(height, k) << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Helper function for recursion with memoization
    private int func(int ind, int[] heights, int k, int[] dp) {
        // Base case
        if (ind == 0) {
            return 0;
        }
        
        /* If the result for this index has been 
        previously calculated, return it*/
        if (dp[ind] != -1) {
            return dp[ind];
        }
        
        // Initialize mmStep to Integer.MAX_VALUE
        int mmStep = Integer.MAX_VALUE;
        
        // Try all possible jumps
        for (int j = 1; j <= k; j++) {
            
            // Check if ind - j is non-negative
            if (ind - j >= 0) {
                int jump = func(ind - j, heights, k, dp) + Math.abs(heights[ind] - heights[ind - j]);
                
                //Update the minimum energy
                mmStep = Math.min(jump, mmStep);
            }
        }
        
        // Store the result in dp array and return
        dp[ind] = mmStep;
        return dp[ind];
    }
    
    /* Function to find the minimum 
    energy to reach the last stair*/
    public int frogJump(int[] heights, int k) {
        int ind = heights.length - 1;
        
        /* Initialize a memoization array
        to store calculated results*/
        int[] dp = new int[ind + 1];
        Arrays.fill(dp, -1);
        
        // Return the minimum energy
        return func(ind, heights, k, dp);
    }
    
    public static void main(String[] args) {
        int[] heights = {15, 4, 1, 14, 15};
        int k = 3;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Print the answer
        System.out.println("Minimum energy: " + sol.frogJump(heights, k));
    }
}
class Solution:
    #Function for recusion using memoization
    def func(self, ind, heights, k, dp):
        # Base case
        if ind == 0:
            return 0
        
        """ If the result for this index has been
        previously calculated, return it"""
        if dp[ind] != -1:
            return dp[ind]
        
        # Initialize mmStep to float('inf')
        mmStep = float('inf')
        
        # Try all possible jumps
        for j in range(1, k + 1):
            # Check if ind - j is non-negative
            if ind - j >= 0:
                jump = self.func(ind - j, heights, k, dp) + abs(heights[ind] - heights[ind - j])
                
                #Update the minimum energy
                mmStep = min(mmStep, jump)
        
        # Store the result in dp array and return
        dp[ind] = mmStep
        return dp[ind]
    
    def frogJump(self, heights, k):
        ind = len(heights) - 1
        
        """ Initialize a memoization array
        to store calculated results"""
        dp = [-1] * (ind + 1)
        
        # Return the minimum energy
        return self.func(ind, heights, k, dp)
    
if __name__ == "__main__":
    heights = [15, 4, 1, 14, 15]
    k = 3
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the answer
    print("Minimum energy:", sol.frogJump(heights, k))
class Solution {
    // Helper function for recursion with memoization
    func(ind, heights, k, dp) {
        // Base case
        if (ind === 0) {
            return 0;
        }
        
        /* If the result for this index has been
        previously calculated, return it*/
        if (dp[ind] !== -1) {
            return dp[ind];
        }
        
        // Initialize mmStep to Infinity
        let mmStep = Infinity;
        
        // Try all possible jumps
        for (let j = 1; j <= k; j++) {
            // Check if ind - j is non-negative
            if (ind - j >= 0) {
                let jump = this.func(ind - j, heights, k, dp) + Math.abs(heights[ind] - heights[ind - j]);
                
                //Update the minimum energy
                mmStep = Math.min(jump, mmStep);
            }
        }
        
        // Store the result in dp array and return
        dp[ind] = mmStep;
        return dp[ind];
    }
    
    /* Function to find the minimum 
    energy to reach the last stair*/
    frogJump(heights, k) {
        let ind = heights.length - 1;
        
        /* Initialize a memoization array
        to store calculated results*/
        let dp = new Array(ind + 1).fill(-1);
        
        // Return the minimum energy
        return this.func(ind, heights, k, dp);
    }
}
    let heights = [15, 4, 1, 14, 15];
    let k = 3;
    
    // Create an instance of Solution class
    let sol = new Solution();
    
    // Print the answer
    console.log("Minimum energy:", sol.frogJump(heights, k));

Complexity Analysis:

Time Complexity: O(k*N),The function is called recursively for each index from N-1 down to 0. For each index, the function explores up to k possible jumps, where N is the length of the heights array.

Space Complexity:O(N)+O(N), We are using a recursion stack space O(N) and an array (again O(N)). Therefore total space complexity will be O(N) + O(N) ≈ O(N).

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Bottom-Up Approach in Tabulation: Tabulation involves solving a problem by building a solution from the bottom up. This means start with the smallest subproblems and iteratively compute solutions for larger subproblems until the desired solution has been found.
Declare an Array dp[] of Size n: Here, n is the size of the array. It represents the solution to the subproblem for any given index.
Setting Base Cases in the Array:In the recursive code, we knew the answer for base case, when N = 0, we had only one choice, to stay at 0 and that takes 0 energy. Similarly if we are computing in tabulation, we definitely know that the answer for dp[0] = 0.
Iterative Computation Using a Loop: Set an iterative loop that traverses the array( from index 1 to n-1). To compute the solution for larger values, use a loop that iterates from the smallest subproblem up to n.
Explanation of dp[i] Calculation: The current value(dp[i]) represents the subproblem and by the recurrence relation it is obvious that dp[i] is calculated by considering all possible 'k' previous stairs, from where the frog could jump to i.
Choosing the minimum: Among all the computed energies for each jump(from 1 to k), dp[i] is set to the minimum value. This ensures that dp[i] holds the minimum energy required.
Returning the last element: The last element of the dp array is returned because it holds the optimal solution to the entire problem after the bottom-up computation has been completed.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the mimimum 
    energy to reach last stair*/
    int frogJump(vector<int> &heights, int k) {
        int ind = heights.size();

        /*Initialize a memoization array
        to store calculated results*/
        vector<int> dp(ind + 1, -1);

        dp[0] = 0;

        // Loop through the array 
        for (int i = 1; i < ind; i++) {
            int mmSteps = INT_MAX;

            // Loop to try all possible jumps from '1' to 'k'
            for (int j = 1; j <= k; j++) {
                if (i - j >= 0) {
                    int jump = dp[i - j] + abs(heights[i] - heights[i - j]);
                    
                    //Update the Minimum energy
                    mmSteps = min(jump, mmSteps);
                }
            }
            dp[i] = mmSteps;
        }
        //Result is stored in the last element of dp
        return dp[ind - 1]; 

    }
};

int main() {
    vector<int> height {15,4,1,14,15};
    int k = 3;

    // Create an instance of Solution class
    Solution sol;

    // Print the answer
    cout << "Minimum energy : " << sol.frogJump(height, k) << endl;

    return 0;
}
import java.util.*;

class Solution {
    /* Function to find the minimum 
    energy to reach the last stair*/
    public int frogJump(int[] heights, int k) {
        int ind = heights.length;
        
        /* Initialize a memoization array
        to store calculated results*/
        int[] dp = new int[ind + 1];
        Arrays.fill(dp, -1);
        
        dp[0] = 0; 
        
        // Loop through the array
        for (int i = 1; i < ind; i++) {
            int mmSteps = Integer.MAX_VALUE;
            
            // Loop to try all possible jumps from 1 to k
            for (int j = 1; j <= k; j++) {
                if (i - j >= 0) {
                    int jump = dp[i - j] + Math.abs(heights[i] - heights[i - j]);
                    
                    //Update the minimum energy
                    mmSteps = Math.min(jump, mmSteps);
                }
            }
            
            dp[i] = mmSteps;
        }
        
        // Result is stored in the last element of dp
        return dp[ind - 1];
    }
    
    public static void main(String[] args) {
        int[] heights = {15, 4, 1, 14, 15};
        int k = 3;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Print the answer
        System.out.println("Minimum energy: " + sol.frogJump(heights, k));
    }
}
class Solution:
    def frogJump(self, heights, k):
        ind = len(heights)
        
        """ Initialize a memoization array 
        to store calculated results"""
        dp = [-1] * (ind + 1)
        dp[0] = 0  
        
        # Loop through the array
        for i in range(1, ind):
            mmSteps = float('inf')
            
            # Loop to try all possible jumps from 1 to k
            for j in range(1, k + 1):
                if i - j >= 0:
                    jump = dp[i - j] + abs(heights[i] - heights[i - j])
                    
                    #Update the minimum energy
                    mmSteps = min(jump, mmSteps)
            
            dp[i] = mmSteps
        
        # Result is stored in the last element of dp
        return dp[ind - 1]
    
if __name__ == "__main__":
    heights = [15, 4, 1, 14, 15]
    k = 3
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Print the answer
    print("Minimum energy:", sol.frogJump(heights, k))
class Solution {
    /* Function to find the minimum 
    energy to reach the last stair*/
    frogJump(heights, k) {
        let ind = heights.length;
        
        /* Initialize a memoization array 
        to store calculated results*/
        let dp = new Array(ind + 1).fill(-1);
        dp[0] = 0; // Base case
        
        // Loop through the array
        for (let i = 1; i < ind; i++) {
            let mmSteps = Infinity;
            
            // Loop to try all possible jumps from 1 to k
            for (let j = 1; j <= k; j++) {
                if (i - j >= 0) {
                    let jump = dp[i - j] + Math.abs(heights[i] - heights[i - j]);
                    mmSteps = Math.min(jump, mmSteps);
                }
            }
            
            dp[i] = mmSteps;
        }
        
        // Result is stored in the last element of dp
        return dp[ind - 1];
    }
}

    let heights = [15, 4, 1, 14, 15];
    let k = 3;
    
    // Create an instance of Solution class
    let sol = new Solution();
    
    // Print the answer
    console.log("Minimum energy:", sol.frogJump(heights, k));

Complexity Analysis:

Time Complexity: O(N*k), where N is the given size of given array. As for each element of the array, we are considering all possible steps from 1 to k.

Space Complexity:O(N), an additional array dp of size n is used to store intermediate results. Hence, the space complexity is O(N).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Why greedy approach will not work:

Complexity Analysis:

Complexity Analysis:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code