Frog 1 — tại sao animation dạy DP tốt hơn text tĩnh

AtCoder Educational DP Contest · A — Frog 1 · $h = [30, 10, 60, 10, 60, 50]$ · đáp án $= 40$

Đây là lời giải tĩnh trên usaco.guide — bạn hiểu được bao nhiêu chỉ bằng cách đọc?

// Pull DP
dp[0] = 0;
for (int i = 1; i < N; i++) {
    if (i - 1 >= 0)
        dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
    if (i - 2 >= 0)
        dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
}
cout << dp[N-1];

Câu hỏi text không trả lời được: Tại sao phải xét cả hai dp[i-1] và dp[i-2]? Tại sao không dùng greedy? Cost tích luỹ khi nào? Đường đi tối ưu là gì?

Step 1 / 12

STEP 1 — SETUP

Điều khiển: ← → step · Space play/pause · Home End đầu/cuối (click vào widget để focus)

Animation dạy được điều mà text không dạy được

1. min() như một cuộc đua

Hai ứng viên cùng xuất hiện, có số cost cụ thể, cái thấp hơn thắng và chui vào ô dp. Text chỉ viết min(A, B) — bạn không thấy được 2 con số thực.

2. Khoảnh khắc zero-cost

Stone 1 và 3 cùng cao 10 → cost $= |10-10| = 0$. Khi frog "bay miễn phí" giữa 2 cột cùng cao, bạn sẽ nhớ mãi rằng |h[i]-h[j]| = 0 khi cao bằng nhau.

3. Vì sao greedy sai

Greedy "nhảy đến cột gần độ cao nhất" chọn 1→2 (cost 20) rồi kẹt ở đường xấu. DP skip hẳn stone 2 để lấy đường 1→3→5→6. Cực khó thấy khi đọc code.

4. Backtrack để có path

dp[] chỉ cho biết chi phí. Để biết đi đường nào, phải nhớ parent pointer rồi lần ngược từ $N$ về $1$. Animation làm bước này hiện ra thay vì ẩn trong code.