AtCoder Educational DP Contest Frog 1

Problem Link: 
https://atcoder.jp/contests/dp/tasks/dp_a

Problem Statement

There are $N$ stones, numbered $1,2,\dots ,N$. For each $i$ ($1\le i\le N$), the height of Stone $i$ is $h_i$.

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.

Find the minimum possible total cost incurred before the frog reaches Stone $N$.

Constraints

• All values in input are integers.
• $2\le N\le {10}^5$
• $1\le h_i\le {10}^4$

Input

Input is given from Standard Input in the following format:

$N$
$h_1$ $h_2$ $\dots$ $h_N$

Output

Print the minimum possible total cost incurred.

Sample Input 1 Copy

Copy

4
10 30 40 20

Sample Output 1 Copy

Copy

30

If we follow the path $1$ → $2$ → $4$, the total cost incurred would be $|10-30|+|30-20|=30$.

Sample Input 2 Copy

Copy

2
10 10

Sample Output 2 Copy

Copy

0

If we follow the path $1$ → $2$, the total cost incurred would be $|10-10|=0$.

Sample Input 3 Copy

Copy

6
30 10 60 10 60 50

Sample Output 3 Copy

Copy

40

If we follow the path $1$ → $3$ → $5$ → $6$, the total cost incurred would be $|30-60|+|60-60|+|60-50|=40$.

Solution:

This problem can be solved using dynamic programming.

Let dp[i] be the minimum total cost to reach i^th stone.
Then :

dp[i] =  min(dp[i - 2]   + abs(h[i] - h[i - 2] , 

                       dp[i - 1] + abs(h[i] - h[i - 1]]);

For 0th and 1st stones:

  dp[0] = 0;

dp[1] = abs(h[1] - h[0])

Implementation