Hướng dẫn thuật toán - Đăng - Chuyên Sơn La Online Judge

1. Phân tích sự khác biệt

Ở bài FROG1: Từ tảng đá , bạn chỉ có thể nhảy đến hoặc (tối đa 2 bước).
Ở bài FROG2: Từ tảng đá , bạn có thể nhảy đến bất kỳ tảng đá nào trong khoảng từ đến (tối đa bước).

Nhận xét: Thay vì chỉ có 2 sự lựa chọn như trước, bây giờ tại mỗi bước, con ếch có tới sự lựa chọn. Tuy nhiên, tư duy Quy hoạch động vẫn hoàn toàn áp dụng được.

2. Tư duy thuật toán

Chúng ta vẫn 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ở:
- dp[1] = 0 (Con ếch bắt đầu ở đây).
- Các vị trí khác khởi tạo bằng một số rất lớn (vô cùng) để lát nữa ta tìm giá trị nhỏ nhất.
Công thức truy hồi (Mở rộng): Để đến được tảng đá thứ , con ếch có thể đã nhảy đến từ một trong các tảng đá trước đó: .

Với mỗi khoảng cách nhảy (từ đến ):
- Nếu tảng đá tồn tại (tức là ):
  - Chi phí = (Chi phí thấp nhất đến ) + (Chi phí nhảy từ sang ).
  - Công thức: dp[i-j] + |h[i] - h[i-j]|
=> Kết quả dp[i] sẽ là giá trị nhỏ nhất trong tất cả các khả năng nhảy từ tảng đá phía trước đó.

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

Nhập dữ liệu: Đọc và mảng chiều cao .
Khởi tạo:
- Tạo mảng dp kích thước .
- Đặt tất cả dp[i] bằng một giá trị rất lớn (ví dụ: 1,000,000,000).
- Đặt dp[1] = 0.
Tính toán (Dùng 2 vòng lặp lồng nhau):
- Vòng lặp ngoài: Duyệt từng tảng đá từ đến .
- Vòng lặp trong: Duyệt từng bước nhảy từ đến .
  - Kiểm tra nếu :
    - Cập nhật dp[i] = nhỏ_nhất(dp[i], dp[i-j] + tuyệt_đối(h[i] - h[i-j])).
Kết quả: In ra giá trị dp[N].

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

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

Khai báo mảng dp[N+1]
Lấp đầy dp bằng giá trị VÔ_CÙNG
dp[1] = 0

Cho i chạy từ 2 đến N:
    Cho j chạy từ 1 đến K:
        Nếu (i - j >= 1):
            Chi_phí_mới = dp[i-j] + tuyệt_đối(h[i] - h[i-j])
            dp[i] = nhỏ_nhất(dp[i], Chi_phí_mới)

In ra dp[N]

5. Đánh giá độ phức tạp

Thời gian: Chúng ta có 2 vòng lặp lồng nhau: vòng ngoài chạy lần, vòng trong chạy tối đa lần. Tổng cộng khoảng phép tính.
Với và , số phép tính là (10 triệu). Máy tính hiện đại có thể xử lý khoảng phép tính mỗi giây, nên thuật toán này sẽ chạy rất nhanh (dưới 1 giây).

Lời khuyên: Khi lập trình bài này, hãy đảm bảo giá trị "Vô cùng" bạn chọn đủ lớn để không bị nhỏ hơn kết quả thực tế (với bài này, là con số an toàn).