# 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).

*/