Frog Jump

Frog Jump

/*

*** Using Recursion :-

Time Complexity :- O(2^N)
Space Complexity:- O(N)

1. Break the problem in terms of indexes and observed over the questions.
2. Do computational work over the indexes , as here , based on indexes.
3. Compute the minimum energy required by the frog to jump from 1 to Nth stair.

*/

/*
Memoization Approach:-

Time Complexity:- O(N)
Space Complexity:- O(N) for Arraty + O(N) for recurssion stack

Note :- Break the recursive solution , in form of recurrence relation
so that whenever the same function call , if it found in the array we
maintain just return their value , as we using extra N size space for that.

*/

/*
Tabulation Approach:-

Time Complexity:- O(N)
Space Complexity :- O(N)

For the Tabulation , approach , we go from bottom up , as solving question
form base case to required answer , and use it further to solve another bigger problem.
We declared the dp in it and used it , and move optimally and storing minimum energy used to move ahead , and last index of dp array contain minimum amount of energy from moving 1 to Nth Chair.

*/

/*
Optimizing Space:-

Time Complexity:- O(N)
Space Complexity:- O(1)

Now we see , that we are moving 1 or 2 index at most at single time , so
instead of maintain the array , Now we maintain two variable which use constant space, as we only need to return minimum total energy which for nth position stored at n-1 idx , so i,e here in prev , and updating prev and prev1 after each iteration.

Using this we optimized the space from O(N) to O(1).

*/

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store