Question 5: There are N stones, numbered 1, 2, \ldots, N. For each (1…

There are $N$ stones, numbered $1, 2, \ldots, N$. For each $(1 \leqslant i \leqslant N)$, the height of stone $i$ is $h_i$. Assume these heights are stored in an array $H$.

There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone $N$:

• If the frog is currently on Stone $i$, jump to Stone $i+1$ or Stone $i+2$.
• Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Our goal is to find the minimum possible total cost incurred before the frog reaches Stone $N$.

Towards solving this problem, note that the frog, can jump to only (i + 1) or (i + 2) from a position i. We will now try to define a recurrence that leads us to the solution.

For all $1 \leqslant i \leqslant N$, define dp[i] as the minimum cost we can achieve to reach stone i. For our base cases, note that we have the following:

• dp[0] = 0 and
• dp[1] = abs(H[1] − H[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Based on the above data, answer the given subquestions.

Which of the following is a valid recurrence for dp[i]?