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.
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.
For each test case, return an integer corresponding to the minimum energy lost to reach the last stair.
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 10 1 <= N <= 100000. 1 <= HEIGHTS[i] <= 1000 . Time limit: 1 sec
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.