Redaksiya

Let $d p [i]$ be the minimum cost of moving the frog to stone $i$ . Then:

$d p [1] = 0$ (no need to move anywhere),
$d p [2] = ∣ h_{2} - h_{1} ∣$ ;

The frog can jump to the $i (i \geq 3)$ -th stone:

either from the $(i - 1)$ -th stone with a cost of $∣ h_{i} - h_{i - 1} ∣$ ;
or from the $(i - 2)$ -th stone with a cost of $∣ h_{i} - h_{i - 2} ∣$ ;

Hence

d p [i] = min (d p [i - 1] + ∣ h_{i} - h_{i - 1} ∣, d p [i - 2] + ∣ h_{i} - h_{i - 2} ∣)

Example

For the given example, the frog’s path with a cost of $20 + 10 = 30$ looks like:

$d p [1] = 0$ ;
$d p [2] = ∣ h_{2} - h_{1} ∣ = ∣30 - 10∣ = 20$ ;
$d p [3] = min (d p [2] + ∣ h_{3} - h_{2} ∣, d p [1] + ∣ h_{3} - h_{1} ∣) = min (20 + ∣40 - 30∣, 0 + ∣40 - 10∣) = min (30, 30) = 30$ ;
$d p [4] = min (d p [3] + ∣ h_{4} - h_{3} ∣, d p [2] + ∣ h_{4} - h_{2} ∣) = min (30 + ∣20 - 40∣, 20 + ∣20 - 30∣) = min (50, 30) = 30$ ;

Exercise

Fill the $d p$ array for the following example:

Algorithm realization

Declare the arrays.

#define MAX 100001
int h[MAX], dp[MAX];

Read the input data. Store the heights of the stones in the array $h$ .

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%d", &h[i]);

Initialize the values of $d p [1]$ and $d p [2]$ .

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

Compute the values of $d p [i] (3 \leq i \leq n)$ .

for (i = 3; i <= n; i++)
{
  a = dp[i - 1] + abs(h[i] - h[i - 1]);
  b = dp[i - 2] + abs(h[i] - h[i - 2]);
  dp[i] = min(a, b);
}

Print the answer.

printf("%d\n", dp[n]);

Java realization

import java.util.*;
 
class Main
{
  static int h[], dp[];
 
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    h = new int[n+1];
    dp = new int[n+1];
    for(int i = 1; i <= n; i++)
      h[i] = con.nextInt();
   
    dp[1] = 0;  dp[2] = Math.abs(h[2] - h[1]);
    for (int i = 3; i <= n; i++)
    {
      int a = dp[i - 1] + Math.abs(h[i] - h[i - 1]);
      int b = dp[i - 2] + Math.abs(h[i] - h[i - 2]);
      dp[i] = Math.min(a, b);
    }
 
    System.out.println(dp[n]);
    con.close();
  }
}

Python realization

Read the input data. Store the heights of the stones in the list $h$ .

n = int(input())
h = list(map(int, input().split()))

Initialize the list $d p$ and assign values to $d p [1]$ and $d p [2]$ .

dp = [0] * (n + 1)
dp[1] = 0
dp[2] = abs(h[1] - h[0])

Compute the values of $d p [i] (3 \leq i \leq n)$ .

for i in range(3, n + 1):
  a = dp[i - 1] + abs(h[i - 1] - h[i - 2])
  b = dp[i - 2] + abs(h[i - 1] - h[i - 3])
  dp[i] = min(a, b)

Print the answer.

print(dp[n])