Thuật toán quy hoạch động được ưa chuộng bởi vì ban đầu, bài toán có muôn hình vạn trạng và bạn phải suy nghĩ rất nhiều mới tìm ra được lời giải. Không có một công thức chuẩn mực nào áp dụng được cho mọi bài toán. Bởi vì sự phổ biến của nó, bạn bắt buộc phải cực kỳ thuần thục thuật toán này nếu muốn có kết quả tốt trong các cuộc thi. Series Quy hoạch động cho người mới bắt đầu gồm 6 phần, chia ra làm hai hướng tiếp cận:
1. Khi nào thì dùng quy hoạch động
Khi nào thì chúng ta cần đến quy hoạch động? Đó là một câu hỏi rất khó trả lời. Không có một công thức nào cho các bài toán như vậy. Tuy nhiên, có một số tính chất của bài toán mà bạn có thể nghĩ đến quy hoạch động. Dưới đây là hai tính chất nổi bật nhất trong số chúng:
- Bài toán có các bài toán con gối nhau (bài toán có công thức quy nạp giống trong toán học): Sử dụng kết quả của bài toán nhỏ để giải quyết bài toán lớn (bài toán chia để trị)
- Bài toán có cấu trúc con tối ưu
2. Bài toán Đường đi có tổng lớn nhất
Link đề bài: Đường đi có tổng lớn nhất
Yêu cầu đề bài: Xác định cách để đi từ ô bất kỳ thuộc cột (1) đến ô bất kỳ thuộc cột (n) sao cho tổng các ô trên đường đi là lớn nhất.
Xác định các bước giải bài toán (làm ra nháp)
Bước 1: Xác định ý nghĩa hàm đệ quy
Gọi (dp(i,j)) là tổng đường đi lớn nhất khi đang đứng tại ô ((i,j))
Mảng (F[i][j]) lần này sẽ không khởi tạo bằng giá trị (-1) được nữa, do trên bảng xuất hiện cả những số âm, ta khởi tạo giá trị là (-INF=-2e9), là giá trị mà kết quả không bao giờ đạt được.
Bước 2: Xác định điều kiện dừng đệ quy
- Nếu đang đứng tại ô nào đó tại cột (n), tức là (j=n), ta sẽ không đi nữa, kết quả trả về chính giá trị tại ô đang đứng if (j = n) (return) (a[i][j];)
- Nếu đi vào một ô nào đó nằm ngoài bảng, coi bước đi này là không hợp lệ, kết quả trả về (-INF) if ((i) < (1 || i > m)) (return) (-1e9;)
Bước 3: Xác định công thức tính
Ô ((i,j)) sẽ đi tới được các ô: ((i-1,j+1), (i, j+1), (i+1, j+1)). Vậy sẽ có 3 cách đi:
- Cách 1: Đi từ ô ((i,j)) đến ô ((i-1, j+1)) : (dp(i-1,j+1) + a[i][j])
- Cách 2: Đi từ ô ((i,j)) đến ô ((i, j+1)): (dp(i,j+1) + a[i][j])
- Cách 3: Đi từ ô ((i,j)) đến ô ((i+1, j+1)): (dp(i+1,j+1) + a[i][j])
Vậy ta có công thức: (F[i][j] = max(dp(i-1,j+1), dp(i,j+1), dp(i+1,j+1)) + a[i][j] )
Bước 4: Xác định kết quả nằm ở đâu? Kết quả nằm ở: (max(dp(i,1)) với mọi (i = 1 → m) - ô xuất phát là ô bất kỳ thuộc cột (1)
3. Bài toán cái túi - Knapsack
Link đề bài: Atcoder Educational DP Contest D - Knapsack 1
Yêu cầu đề bài: Xác định cách lấy các đồ vật sao cho tổng trọng lượng các đồ vật không quá (W) và giá trị của các đồ vật là lớn nhất.
Xác định các bước giải bài toán
Bước 1: Xác định ý nghĩa hàm đệ quy
Gọi (dp(i, t)) là tổng giá trị lớn nhất thu được khi đang xét đồ vật (i), tổng trọng lượng các đồ vật đã lấy là (t), các đồ vật từ (1) tới (i-1) đã xét chọn/không chọn rồi.
Mảng (F) được khởi tạo giá trị (-1) - do giá trị các đồ vật đều dương, cùng lắm ta không chọn được đồ vật nào thì tổng giá trị bằng (0)
Bước 2: Xác định điều kiện dừng đệ quy
- Nếu (i > n) (return) (0), đã xét hết các đồ vật từ (1) tới (n) thì dừng việc lấy.
Bước 3: Xác định công thức tính
Khi xét đến đồ vật thứ (i), ta có hai trường hợp:
- Trường hợp 1: Không chọn đồ vật (i): Nếu không chọn đồ vật này, trọng lượng vẫn là (t), xét đồ vật tiếp theo: (dp(i+1,t))
- Trường hợp 2: Chọn đồ vật (i) - Điều kiện là (t+w[i] leq W) Chọn đồ vật này, trọng lượng chiếc túi đang là (t) sẽ biến thành (t + w[i]), giá trị được tăng thêm (v[i]): (dp(i+1, t+w[i]) + v[i])
Vậy ta có công thức: (dp(i,t)=left{begin{matrix} dp(i+1,t)& text{nếu } t+w[i]>W\ max(dp(i+1, t), dp(i+1, t+w[i]) + v[i])& text{nếu } t+w[i] leq W& end{matrix}right)
Bước 4: Xác định kết quả nằm ở đâu? Kết quả nằm ở: (dp(1,0)) - Xét bắt đầu từ đồ vật (1), ban đầu chiếc túi có trọng lượng là (0).
4. Bài toán Xâu con chung dài nhất
Link đề bài: Atcoder Educational DP Contest F - LCS
Yêu cầu đề bài: Xác định xâu con chung (không liên tiếp) dài nhất của hai xâu (s) và (t) cho trước.
Bài tập này yêu cầu truy vết kết quả. Tuy nhiên ở bài viết này sẽ chỉ đề cập đến việc tìm độ dài xâu con chung dài nhất trước, sau khi tìm được độ dài dài nhất rồi ta sẽ sử dụng kết quả của mảng quy hoạch động để tìm ra xâu con chung dài nhất đó.
Xác định các bước giải bài toán
Bước 0: Khởi tạo bài toán
- Gọi (n) là độ dài của xâu (s)
- Gọi (m) là độ dài của xâu (t)
- Để việc xử lý cho tiện, ta sẽ thêm một ký tự # ở đầu mỗi xâu, khi đó ký tự bắt đầu của một xâu là 1.
Bước 1: Xác định ý nghĩa hàm đệ quy
- Gọi (dp(i,j)) là độ dài xâu con chung dài nhất khi đang xét đến vị trí (i) của xâu (s) và vị trí (j) của xâu (t)
- Mảng (F) được khởi tạo giá trị (-1)
Bước 2: Xác định điều kiện dừng đệ quy
- Nếu (i) hoặc (j) lớn hơn độ dài xâu (s) và (t) tương ứng, nghĩa là từ đây không thể trùng được nữa. Kết quả trả về 0.
Bước 3: Xác định công thức truy hồi
- Khi xét vị trí (i) của xâu (s) và vị trí (j) của xâu (t), ta có hai trường hợp:
- Trường hợp 1: (s[i] = t[j]) Hai xâu sẽ trùng nhau ký tự (s[i]). Vậy ta xét tiếp vị trí (i + 1) và (j + 1): (dp(i,j) = dp(i+1,j+1) + 1)
- Trường hợp 2: (s[i] neq t[j]): Một trong hai ký tự sẽ không thuộc xâu con chung: (dp(i,j) = max(dp(i+1,j), dp(i,j+1)))
Vậy ta có công thức: (dp(i,j)=left{begin{matrix} dp(i+1,j+1) + 1 & text{nếu } s[i] = t[j]\ max(dp(i+1,j), dp(i,j+1))& text{nếu } s[i] neq t[j]& end{matrix}right)
Bước 4: Xác định kết quả nằm ở đâu? Kết quả nằm ở: (dp(1,1)) - xét bắt đầu từ các ký tự đầu tiên của hai xâu.
5. Bài toán Dãy con tăng dài nhất
Link đề bài: Dãy con tăng dài nhất (bản dễ)
Yêu cầu đề bài: Xác định dãy con tăng (không liên tiếp) dài nhất của dãy (a).
Xác định các bước giải bài toán
Bước 1: Xác định ý nghĩa hàm đệ quy
- Gọi (dp(i, j)) là độ dài dãy con tăng dài nhất khi xét đến phần tử thứ (i), phần tử cuối cùng trong dãy con tăng đã kết nạp là phần từ (j)
- Mảng (F) được khởi tạo giá trị (-1)
Bước 2: Xác định bài toán con
- Nếu (i > n ), ta đã xét hết các phần tử, kết quả trả về 0.
Bước 3: Xác định công thức truy hồi
- Khi xét đến phần tử thứ (i), ta có hai trường hợp:
- Trường hợp 1: Không kết nạp phần tử (i) vào dãy con tăng, phần tử tiếp theo cần xét là phần tử i+1, phần tử cuối cùng trong dãy con tăng vẫn là phần tử (j): (dp(i+1, j))
- Trường hợp 2: Kết nạp phần tử (i) vào dãy con tăng - xét điều kiện (a[i] > a[j]), lúc đó phần tử cuối cùng trong dãy con tăng sẽ là phần tử (i): (dp(i+1, i) + 1)
Vậy ta có công thức: (dp(i,j)=left{begin{matrix} dp(i+1,j) & text{nếu } a[i] leq a[j]\ max(dp(i+1,j), dp(i+1,i)+1)& text{nếu } a[i] > a[j]& end{matrix}right)
Bước 4: Xác định kết quả nằm ở đâu? Kết quả nằm ở: (dp(1,0)), xét phần tử đầu tiên, lưu ý khởi tạo phần tử (0) của mảng là (-INF) để bất kỳ số nào cũng có thể là số đầu tiên trong dãy con tăng.
Tổng kết
Các bài toán giải quyết bằng Quy hoạch động sử dụng đệ quy có nhớ với cách tiếp cận Top-down, mỗi bài toán sẽ được tính duy nhất 1 lần.
Độ phức tạp của thuật toán quy hoạch động được tính bằng công thức: *Số bài toán Chi phí chuyển trạng thái**
Trong đó:
- Số bài toán: là số phần tử trong mảng (F)
- Chi phí chuyển trạng thái: Độ phức tạp khi triển khai công thức tính mỗi bài toán.
Ví dụ:
- Độ phức tạp của bài toán Đường đi có tổng lớn nhất là (O(mn3)), (m*n) bài toán, mỗi bài toán mất 3 phép tính để triển khai công thức (lấy max của 3 cách đi).
- Độ phức tạp của bài toán Cái túi - Knapsack là (O(nW2), n*W) bài toán, mỗi bài toán mất 2 phép tính để triển khai công thức (2 phép tính tìm max của 2 cách)
- Độ phức tạp của bài toán Xâu con chung dài nhất là (O(m*n))
- Độ phức tạp của bài toán Dãy con tăng dài nhất là (O(n*n)), (n) bài toán con, mỗi bài toán con mất (n) phép tính để thực hiện công thức
Nhận xét
- Khi triển khai bằng cách tiếp cận này, các bạn sẽ không cần phải suy nghĩ xem nên thực hiện bài toán nào trước, bài toán nào sau. Vì bài toán nào chưa được tính thì hàm đệ quy sẽ đi tính nó. Vậy ta có thể nói, tất cả các bài toán quy hoạch động đều có thể giải quyết bằng đệ quy có nhớ được, nhưng chưa chắc đã giải quyết được bằng cách sử dụng vòng lặp for.
- Không cần khởi tạo nhiều tham số lằng nhằng, vì mọi điều kiện của bài toán đều có thể được kiểm soát trong khi triển khai công thức và điều kiện dừng đệ quy.
- Tư duy thuật toán theo cách này cũng thuận với thực tế và đề bài.
Xem thêm các bài trong Series Quy hoạch động cho người mới bắt đầu:
- Quy hoạch động cho người mới bắt đầu (Phần 1) - Sử dụng vòng lặp for cơ bản
- Quy hoạch động cho người mới bắt đầu (Phần 2) - Sử dụng vòng lặp for nâng cao
- Quy hoạch động cho người mới bắt đầu (Phần 3) - Sử dụng vòng lặp for truy vết
- Quy hoạch động cho người mới bắt đầu (Phần 4) - Sử dụng đệ quy có nhớ cơ bản
- Quy hoạch động cho người mới bắt đầu (Phần 5) - Sử dụng đệ quy có nhớ nâng cao
- Quy hoạch động cho người mới bắt đầu (Phần 6) - Sử dụng đệ quy có nhớ truy vết
7. Luyện tập
Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn Unable to display PDF file. Download instead.
