Scriba — frog

Step 1 / 8

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.

Step 2 / 8

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

Step 3 / 8

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

Step 4 / 8

$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$ .

Step 5 / 8

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

Step 6 / 8

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

Step 7 / 8

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

Step 8 / 8

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

frog_foreach