Dynamic programming - linear
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 |
hj| is incurred, where j is the stone to land on.
Find the minimum possible total cost incurred before the frog reaches stone n.
The first line contains number n (2 ≤ n ≤
105). Second line contains integers
hn (1 ≤
Print the minimum possible total cost for frog to reach stone n.
4 10 30 40 20