Hướng dẫn bài toán quy hoạch động
# Quy hoạch động cơ bản (Phần 1) Bài viết có tham khảo và bổ sung, chỉnh sửa từ [TopCoder](https://www.topcoder.com/thrive/articles/Dynamic%20Programming:%20From%20Novice%20to%20Advanced) và một số nguồn khác. **Người viết:** Nguyễn Anh Bảo - Đại học Bách Khoa Hà Nội **Reviewer:** * Hồ Ngọc Vĩnh Phát - Đại học Khoa học Tự nhiên, ĐHQG-HCM * Ngô Nhật Quang - Trường THPT chuyên Khoa học Tự Nhiên, ĐHQGHN ## Giới thiệu __Quy hoạch động (QHĐ) (Dynamic Programming)__ là một trong những kĩ thuật quan trọng và cơ bản nhất trong lập trình thi đấu. Bài viết này sẽ trình bày và giải thích các khái niệm liên quan đến quy hoạch động đồng thời đưa ra các ví dụ minh họa. # Beginner Để mở đầu, ta xét ví dụ sau: ## Ví dụ 1 > *Bạn An có $n$ chiếc ghế màu trắng, $n$ chiếc ghế màu đen và $n$ chiếc ghế màu đỏ. An muốn chọn ra $n$ chiếc ghế để xếp thành một hàng ngang. Do An không thích màu đỏ nên An không muốn xếp hai chiếc ghế đỏ cạnh nhau. Tính số cách xếp ghế thỏa mãn điều kiện đó.* > **Điều kiện:** $1\le n\le 10^5$. ***Lưu ý**: hai cách xếp được xem là khác nhau khi tồn tại một vị trí mà hai cách có hai loại ghế khác nhau.* ![Minh họa](https://i.imgur.com/RUOAYqC.png) Bây giờ ta sẽ xây dựng thuật giải: ### Thuật toán đệ quy Gọi số cách xếp $i$ cái ghế là $f[i]$. Ta xét chiếc ghế thứ $n$. * Nếu nó có màu đen hoặc trắng thì chiếc ghế cạnh nó có thể có một trong ba màu. Do đó ta chỉ cần bố trí $n-1$ chiếc ghế còn lại thỏa mãn yêu cầu. Do có 2 cách chọn màu cho ghế thứ $n$ và $f[n-1]$ cách chọn màu cho các ghế còn lại nên số cách xếp trong trường hợp này là $2 * f[n-1]$. ![Minh họa](https://i.imgur.com/9wsm2Vy.png) * Nếu nó có màu đỏ thì chiếc ghế cạnh nó chỉ có thể có màu trắng hoặc đen. Do vậy nên chiếc ghế thứ $n-2$ có thể có một trong ba màu. Khi đó ta cũng chỉ cần bố trí $n-2$ chiếc ghế còn lại thỏa mãn yêu cầu. Số cách xếp trong trường hợp này là $1* 2* f[n-2]$. ![Minh họa](https://i.imgur.com/EOEataM.png) Với ý tưởng trên, ta có thể giải bài toán này như các bài toán đệ quy đơn giản. Cài đặt như sau: ```cpp= // Tính số cách sắp xếp n cái ghế int solve(int n) { // Trường hợp cơ bản if (n == 1) return 3; if (n == 2) return 8; // Bước đệ quy return 2 * solve(n - 1) + 2 * solve(n - 2); } ``` Thuật toán trên có độ phức tạp lũy thừa nên chỉ áp dụng được với $n$ nhỏ $(n < 45)$, không đủ nhanh so với yêu cầu bài toán. ### Tối ưu thuật toán đệ quy Thuật toán trên chạy chậm vì một số hàm ```solve(i)``` được gọi rất nhiều lần. Ta lấy ví dụ sau: Giả sử cần tính `solve(1000)`. Khi đó cần tính `solve(999)` và `solve(998)`. Để tính `solve(999)` cần gọi hàm `solve(998)` và `solve(997)`. Để tính `solve(998)` cần gọi hàm `solve(997)` và `solve(996)`. Để tính `solve(997)` cần gọi hàm `solve(996)` và `solve(995)`. $\ldots$ Ta có thể biểu diễn các hàm được gọi bằng một sơ đồ như sau: ![Call Graph](https://i.imgur.com/7pGQDNz.png) Từ sơ đồ trên ta thấy có nhiều hàm bị gọi rất nhiều lần một cách không cần thiết: * `solve(998)` được gọi $2$ lần * `solve(997)` được gọi $3$ lần * `solve(996)` được gọi $5$ lần * $\ldots$ Để khắc phục điều này ta có thể sử dụng một mảng nhớ $d$ sao cho $d[i]$ là giá trị của `solve(i)`: ```cpp= int d[100010]; int solve(int n) { if (n == 1) return 3; else if (n == 2) return 8; else if (d[n] != 0) return d[n]; else { d[n] = 2 * f(n - 1) + 2 * f(n - 2); return d[n]; } } ``` Thuật toán trên có độ phức tạp $O(n)$. Với cách tiếp cận trên, ta quan tâm đến giá trị cuối cùng $f[n]$, sau đó mới xem xét những giá trị bé hơn cần thiết cho tính toán. Nhưng với phương pháp quy hoạch động, ta sẽ quan tâm đến các bài toán với tham số nhỏ hơn trước tiên. ## Phương pháp tiếp cận ### Khi nào có thể áp dụng QHĐ Quy hoạch động được sử dụng khi ta tìm được công thức liên hệ giữa kết quả bài toán có đầu vào cho trước với một (hoặc một số) bài toán con tương tự nhưng có đầu vào nhỏ hơn. Khi ta biết được một số trạng thái bắt đầu của bài toán, nói cách khác - bài toán con với những đầu vào rất nhỏ, ta có thể sử dụng QHĐ để tính ra kết quả cuối cùng. ### Trạng thái của bài toán là gì? Trạng thái là một trường hợp, một bài toán con của bài toán lớn với tham số cho trước. Ví dụ, trạng thái trong bài này là số cách sắp xếp $n$ chiếc ghế thỏa mãn không có hai ghế đỏ cạnh nhau. ### Liên hệ giữa các trạng thái Để giải bài toán quy hoạch động, điều quan trọng nhất là tìm ra mối liên hệ giữa một trạng thái và các trạng thái có tham số nhỏ hơn. Gọi $f[i]$ là cách sắp xếp $i$ chiếc ghế thành một hàng dọc. Khi đó ta có: \begin{equation} \left\{ \begin{aligned} f[1] =& 3; f[2]=8\\ f[i] =& 2f[i - 1] + 2f[i - 2], \forall i=3;4;\ldots;n(*)\\ \end{aligned} \right. \end{equation} Công thức $(*)$ được gọi là **công thức truy hồi**. ### Tìm kết quả cuối cùng Sau khi đã biết công thức truy hồi và tính được $f[1]$, $f[2]$, ta có thể tìm $f[n]$. ### Code mẫu: ```cpp= include
(Tổng còn lại) |-----|---- $0$|$0$|- $1$|$1$|$1 (0)$ $2$|$2$|$1 (1)$ $3$|$1$|$3 (0)$ $4$|$2$|$1 (3)$ $5$|$1$|$5 (0)$ $6$|$2$|$3 (3)$ $7$|$3$|$1 (6)$ $8$|$2$|$3 (5)$ $9$|$3$|$1 (8)$ $10$|$2$|$5 (5)$ $11$|$3$|$1 (10)$ ### Code tham khảo: ```cpp= |