Cách nghĩ Quy hoạch động, bài FROG 1 - Atcoder

Bài FROG 1 là một bài tập Quy hoạch động cơ bản, nằm trong danh sách các bài tập thuộc kì thi DP Contest tại Atcoder. Hôm nay chúng ta cùng nhau phân tích cách nghĩ để giải bải Frog 1 bằng Quy hoạch động. Mục đích là muốn thực hành lại các bước tư duy thuật toán theo mô hình Quy hoạch động đã được trình bày ở một bài viết trước.

Tóm tắt bài FROG 1: Có N hòn đá được đánh số từ 1 tới N. Ban đầu chú ếch ngồi ở hòn đá 1. Tại hòn đá i, chú ếch có thể nhảy tới hòn đá (i+1) hoặc (i+2); và chú sẽ mất chi phí là |h[i]-h[j]| với j là hòn đá đích mà chú ếch nhảy tới. Hãy tìm chi phí tối thiểu để chú ếch có thể nhảy tới hòn đá N?

Ở giai đoạn ban đầu làm quen với Quy hoạch động, ta xem xét các bài toán có dấu hiệu giải được bằng phương pháp QHĐ trước để học cách phân tích (tư duy Quy hoạch động), nên tạm thời ta sẽ bỏ qua bước xác định xem bài toán liệu có thể giải được bằng phương pháp QHĐ.

1. Định nghĩa hàm Quy hoạch động: Bài toán yêu cầu tính chi phí tối thiểu để nhảy tới hòn đá N, ta gọi F(n) là chi phí tối thiểu đó. Tại mỗi hòn đá, chi phí tối thiểu để tới đó chỉ phụ thuộc vào vị trí hòn đá.
2. Xác định công thức quy hoạch động: Giả sử con ếch đang đứng ở hòn đá i. Khi đó chi phí tối thiểu tới được đó là F(i); để tới được hòn đá i, con ếch chỉ có thể nhảy từ hòn đá (i-1) với chi phí là |h[i-1]-h[i]| hoặc từ hòn đá (i-2) với chi phí là |h[i-2]-h[i]| và như vậy, chi phí tối thiểu để có thể tới được bậc i là F(i)=min(F(i-1)+|h[i-1]-h[i]|, F(i-2)+|h[i-2]-h[i]|)
3. Xác định các cơ sở Quy hoạch động: tại vị trí i=1, hòn đá đầu tiên, chi phí để tới được đó hiển nhiên là F(1)=0; Để tới được hòn đá 2, chi phí tới đó sẽ bằng chi phí tới được hòn đá 1 là F(1) cộng với chi phí nhảy từ hòn đá 1 lên hòn đá 2: F(2)=F(1)+|h[1]-h[2]|)
4. Bảng phương án: Ta lưu các giá trị F(i) bằng mảng 1 chiều F[i]; tính và điền trước giá trị F[1], F[2] --> Lần lượt tính các F[i] với i từ 3 tới n. Vì quá trình nhảy kết thúc tại hòn đá N nên kết quả bài toán cần đưa ra là F[n]
5. Cách code để tính các F[i]: dùng vòng lặp để tính bình thường thôi.

Code mẫu: Test thử bài FROG 1 tại vnoj

for (int i = 3; i <= n; i ++)
 dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
cout << dp[n];