# Frog Jump

Posted: 17 Dec, 2021
Difficulty: 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 |HEIGHT[i-1] - HEIGHT[j-1] |.In 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
`````` Approach 1

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’.