Жабка (Розбір)

Нехай $dp[i]$ містить найменшу вартість переміщення жаби на камінь $i$. Тоді:

• dp[1] = 0 (переміщатися нікуди не треба),

• dp[2] = | h_2 - h_1 |;

На i~(i \ge 3)-ий камінь жаба може стрибнути:

• або з (i - 1)-го каменя з вартістю |h_i - h_{i-1}|;

• або з (i - 2)-го каменя з вартістю |h_i - h_{i-2}|;

Звідси

Приклад

Для наведеного прикладу шлях жаби вартістю 20 + 10 = 30 має вигляд:

• dp[1] = 0;

• dp[2] = | h_2 - h_1 | = | 30 - 10 | = 20;

• dp[3] = min( dp[2] + |h_3 - h_2| , dp[1] + |h_3 - h_1| ) = \\ min( 20 + | 40 - 30 | , 0 + | 40 - 10 | ) = min(30, 30) = 30;

• dp[4] = min( dp[3] + |h_4 - h_3| , dp[2] + |h_4 - h_2| ) = \\ min( 30 + | 20 - 40 | , 20 + | 20 - 30 | ) = min(50, 30) = 30;

Вправа

Заповніть масив $dp$ для наступного прикладу:

Реалізація алгоритму

Оголосимо робочі масиви.

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

Читаємо вхідні дані. Висоти каменів заносимо в масив $h$.

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

Ініціалізуємо $dp[1]$ і $dp[2]$.

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

Вираховуємо значення dp[i]~(3 \le i \le 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);
}

Виводимо відповідь.

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

Java реалізація

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 реалізація

Читаємо вхідні дані. Висоти каменів заносимо в список $h$.

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

Ініціалізуємо список $dp$ і присвоюємо значення $dp[1]$ і $dp[2]$.

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

Вираховуємо значення dp[i]~(3 \le i \le 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(dp[n])