Last Updated: 17 Dec, 2021
##### Frog Jump
Easy
Problem statement

#### There is a frog on the '1st' step of an 'N' stairs long staircase. The frog wants to reach the 'Nth' stair. 'HEIGHT[i]' is the height of the '(i+1)th' stair.If Frog jumps from 'ith' to 'jth' stair, the energy lost in the jump is given by absolute value of ( HEIGHT[i-1] - HEIGHT[j-1] ). If the Frog is on 'ith' staircase, he can jump either to '(i+1)th' stair or to '(i+2)th' stair. Your task is to find the minimum total energy used by the frog to reach from '1st' stair to 'Nth' stair.

##### For Example
``````If the given βHEIGHTβ array is [10,20,30,10], the answer 20 as the frog can jump from 1st stair to 2nd stair (|20-10| = 10 energy lost) and then a jump from 2nd stair to last stair (|10-20| = 10 energy lost). So, the total energy lost is 20.
``````
##### Input Format:
``````The first line of the input contains an integer, 'T,β denoting the number of test cases.

The first line of each test case contains a single integer,' Nβ, denoting the number of stairs in the staircase,

The next line contains βHEIGHTβ array.
``````
##### Output Format:
``````For each test case, return an integer corresponding to the minimum energy lost to reach the last stair.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 100000.
1 <= HEIGHTS[i] <= 1000 .

Time limit: 1 sec
``````
Approaches

## 01Approach

In this approach, we will define a recursive function REC(i,HEIGHT) that will return the minimum energy needed to reach the last stair from the ith stair.

The base case will be if i is greater than or equal to βNβ answer will be 0 as we already reached the final stair.

As we have two choices at each step,REC(i) will be the maximum of energy lost for jumping from ith to (i+1)th step + REC(i+1) and energy lost for jumping from i th to (i+2)th step + REC(i+2).

The final answer will be REC(1, HEIGHTS) corresponding to the minimum energy required to reach the last stair from the first stair.

Algorithm:

• Defining 'REC'(i,β HEIGHTSβ) function :
• If i is equal to the length of βHEIGHTSβ - 1:
• Return 0.
• Set βONE_JUMPβ as INF.
• Set βTWO_JUMPβ as INF.
• If i+1 < length of βHEIGHTSβ:
• Set βONE_JUMPβ as abs(HEIGHTS[i]-HEIGHTS[i+1]) + REC(i+1,HEIGHTS).
• If i+2 < length of βHEIGHTSβ:
• Set βTWO_JUMPβ as abs(HEIGHTS[i]-HEIGHTS[i+2]) + REC(i+2,HEIGHTS).
• Set βANSβ as minimum of ONE_JUMP and TWO_JUMP.
• Return βANSβ.
• Set βANSβ as REC(1,HEIGHTS).
• Return βANSβ.