Frog Jump

Posted: 17 Dec, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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