Question 9: 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.