Competitions
Dynamic programming - linear
Frog
There are n stones, numbered 1, 2, ..., n. For each i (1 ≤ i ≤ n), the height of stone i is hi
. There is a frog who is initially on stone 1. It 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 |hi
− hj
| is incurred, where j is the stone to land on.
Find the minimum possible total cost incurred before the frog reaches stone n.
Input
The first line contains number n (2 ≤ n ≤ 105
). Second line contains integers h1
, h2
, ..., hn
(1 ≤ hi
≤ 104
).
Output
Print the minimum possible total cost for frog to reach stone n.
Input example #1
4 10 30 40 20
Output example #1
30