Hướng dẫn thuật toán

Link đến bài tập

1. Phân tích bài toán bằng ngôn ngữ tự nhiên

• Mục tiêu: Tìm cách nhảy từ tảng đá 1 đến tảng đá sao cho tổng "độ mệt" (chi phí) là ít nhất.
• Quy tắc nhảy: Tại mỗi tảng đá, con ếch có 2 lựa chọn:
  1. Nhảy sang tảng đá ngay cạnh nó (cách 1 bước).
  2. Nhảy vượt qua một tảng đá để đến tảng đá tiếp theo (cách 2 bước).
• Chi phí: Mỗi lần nhảy, chi phí tăng thêm một lượng bằng trị tuyệt đối hiệu chiều cao giữa tảng đá đi và tảng đá đến.

Nhận xét quan trọng: Để biết chi phí thấp nhất đến tảng đá thứ , chúng ta chỉ cần biết chi phí thấp nhất để đến được tảng đá thứ và . Đây là dấu hiệu của bài toán Quy hoạch động (Dynamic Programming).

2. Tư duy thuật toán (Quy hoạch động)

Chúng ta sẽ dùng một mảng để lưu trữ kết quả trung gian. Gọi dp[i] là chi phí tối thiểu để con ếch nhảy từ tảng đá 1 đến tảng đá .

• Trạng thái cơ sở (Những gì ta đã biết chắc chắn):

  • Tại tảng đá 1: Con ếch đang ở đây, nên dp[1] = 0.
  • Tại tảng đá 2: Chỉ có một cách duy nhất là nhảy từ tảng đá 1 sang. Do đó: dp[2] = |h[2] - h[1]|.

• Công thức truy hồi (Lựa chọn tối ưu): Để đến được tảng đá thứ (với ), con ếch có hai lựa chọn cuối cùng:

  • Lựa chọn 1: Nhảy từ tảng đá sang .
    • Chi phí = (Chi phí thấp nhất đến ) + (Chi phí nhảy từ sang ).
    • Công thức: dp[i-1] + |h[i] - h[i-1]|
  • Lựa chọn 2: Nhảy từ tảng đá sang .
    • Chi phí = (Chi phí thấp nhất đến ) + (Chi phí nhảy từ sang ).
    • Công thức: dp[i-2] + |h[i] - h[i-2]|

  => Kết quả dp[i] sẽ là giá trị nhỏ nhất trong hai lựa chọn trên.

3. Các bước thực hiện

1. Nhập dữ liệu: Đọc số lượng tảng đá và mảng chiều cao .
2. Khởi tạo: Tạo một mảng dp có kích thước ít nhất là .
3. Thiết lập giá trị ban đầu:
   • dp[1] = 0
   • dp[2] = trị tuyệt đối của (h[2] - h[1])
4. Tính toán: Chạy một vòng lặp từ đến :
   • Tính chi phí nếu nhảy từ .
   • Tính chi phí nếu nhảy từ .
   • Lấy giá trị nhỏ hơn gán vào dp[i].
5. Kết quả: In ra giá trị dp[N].

4. Biểu diễn bằng Pseudo-code (Mã giả)

Nhập N
Nhập mảng h (từ h[1] đến h[N])

Khai báo mảng dp[N+1]

dp[1] = 0
dp[2] = tuyệt_đối(h[2] - h[1])

Cho i chạy từ 3 đến N:
    Cách_1 = dp[i-1] + tuyệt_đối(h[i] - h[i-1])
    Cách_2 = dp[i-2] + tuyệt_đối(h[i] - h[i-2])
    dp[i] = nhỏ_nhất(Cách_1, Cách_2)

In ra dp[N]

5. Ví dụ minh họa với N=4, h={10, 30, 40, 20}

• dp[1] = 0
• dp[2] = |30 - 10| = 20
• dp[3]:
  • Từ đá 2: dp[2] + |40 - 30| = 20 + 10 = 30
  • Từ đá 1: dp[1] + |40 - 10| = 0 + 30 = 30
  • => dp[3] = 30
• dp[4]:
  • Từ đá 3: dp[3] + |20 - 40| = 30 + 20 = 50
  • Từ đá 2: dp[2] + |20 - 30| = 20 + 10 = 30
  • => dp[4] = 30 (Chọn giá trị nhỏ nhất)

Kết quả cuối cùng: 30.