frog

Bai toan Frog 1: co $N=6$ hon da voi do cao $h = [2,9,4,5,1,6]$. Con ech o da $0$, muon nhay den da $N-1$. Moi buoc nhay 1 hoac 2 da, chi phi = $|h_i - h_j|$. Tim chi phi nho nhat.

Co so: $dp[0] = 0$ vi ech bat dau o da $0$, chua ton chi phi nao.

$dp[1]$: chi co the nhay tu da $0$. Chi phi $= dp[0] + |h_1 - h_0| = 0 + |9-2| = 7$.

$dp[2]$: nhay tu da $0$ co chi phi $|4-2| = 2$, tu da $1$ co chi phi $|4-9| = 5$. Tong: $\min(0+2, 7+5) = \min(2, 12) = 2$.

$dp[3]$: tu da $1$: $|5-9| = 4$, tu da $2$: $|5-4| = 1$. Tong: $\min(7+4, 2+1) = \min(11, 3) = 3$.

$dp[4]$: tu da $2$: $|1-4| = 3$, tu da $3$: $|1-5| = 4$. Tong: $\min(2+3, 3+4) = \min(5, 7) = 5$.

$dp[5]$: tu da $3$: $|6-5| = 1$, tu da $4$: $|6-1| = 5$. Tong: $\min(3+1, 5+5) = \min(4, 10) = 4$.

$dp[5] = 4$. Duong di toi uu: $0 \to 2 \to 3 \to 5$ voi chi phi $2 + 1 + 1 = 4$.