New update is available. Click here to update.

Last Updated: 17 Dec, 2021

Easy

```
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
```

Approaches

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

- If i is equal to the length of βHEIGHTSβ - 1:
- Set βANSβ as REC(1,HEIGHTS).
- Return βANSβ.

In this approach, we will use the same recursive functions, we used in approach 1 but we will use memoization to reduce the complexity as the answer for each state will be calculated only once.

We will define an array βDPβ to store the answers and use them to for further reference.

**Algorithm:**

- Defining 'REC'(i,β HEIGHTSβ , βDPβ) function :
- If i equal to the length of βHEIGHTSβ - 1:
- Return 0.

- If DP[i] is not equal to -1:
- The precomputed value was found.
- Return DP[i].

- 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,DP).

- If i+2 < length of βHEIGHTSβ:
- Set βTWO_JUMPβ as abs(HEIGHTS[i]-HEIGHTS[i+2]) + REC(i+2,HEIGHTS,DP).

- Set βANSβ as minimum of ONE_JUMP and TWO_JUMP.
- Set DP[i] as βANSβ.
- Return βANSβ.

- If i equal to the length of βHEIGHTSβ - 1:
- Declare an array DP of size (N+1) to memoize this DP solution.
- Set all values of DP to -1.
- Set βANSβ as REC(1,HEIGHTS,DP).
- Return βANSβ.

In this approach, we will make an array DP of size N+1.DP[i] will denote the minimum energy required to reach the last stair from the ith stair.

The base case will be DP[N] should be equal to zero, as the frog is already at the last stair.

DP[N-1] will be abs(HEIGHTS[N-1] - HEIGHTS[N-2] ) as only one jump is possible.

We will run a loop from N-2 to 1 to compute the values of DP[i] as follows:

Choice 1 will be jumping from i to i+1,So DP[i] will be DP[i+1] + abs(HEIGHTS[i-1]- HEIGHTS[i]).

Choice 2 will be jumping form i to i+2,So DP[i] will be DP[i+2] + abs(HEIGHTS[i-1]- HEIGHTS[i+1]).

For all i, we will pick the minimum of these two choices.

At last, we will return DP[1] as the final answer.

**Algorithm:**

- Declare an array βDPβ of size N+1.
- Set DP[N] as 0.
- Set DP[N-1] as abs(HEIGHTS[N-1] - HEIGHTS[N-2]).
- For i in range N-2 to 1:
- Set ONE_JUMP as DP[i+1] + abs(HEIGHTS[i-1]-HEIGHTS[i]).
- Set TWO_JUMP as DP[i+2] + abs(HEIGHTS[i-1]-HEIGHTS[i+1]).
- Set DP[i] as the minimum of ONE_JUMP and TWO_JUMP.

- Set βANSβ as DP[1].
- Return ANS.