# 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][//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][//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][//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][//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][//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 using namespace std; long long n, f[100010]; int main[] { cin >> n; f[1] = 3; f[2] = 8; for [int i = 3; i **Điều kiện:** $1\le S,N\le1000$ và $1\le v_1,v_2,\dots,v_n\le S$. Ta xây dựng thuật toán QHĐ: Trạng thái của bài toán là số đồng xu nhỏ nhất có tổng giá tiền là $i$. Ta sẽ dùng mảng $f[i]$ để lưu số đồng xu ít nhất có tổng giá trị là $i$, nếu không tồn tại các đồng xu có tổng là $i$ thì gán $f[i] = -1$. Cần một công thức truy hồi để tính $f[i]$ theo $f[1],f[2],\ldots,f[i-1]$. Để ý thấy với $i$ bất kì, nếu có một đồng xu giá trị $v_j \le i$ thì ta có thể thêm đồng đó vào các đồng có tổng giá trị là $i-v_j$. Giả sử $m$ là số đồng xu ít nhất có tổng là $i-v_j$, khi đó có $m+1$ đồng xu có tổng giá trị $i$. Nếu $f[i] = -1$ thì ta cập nhật $f[i] = m + 1$, nếu $f[i] \ne -1$ thì $f[i]=\min[f[i], m+1]$. Sau đây là ví dụ: ***Cho các đồng xu với giá tiền $1,3,5$. Và $S = 11$.*** Đầu tiên, ta bắt đầu từ trạng thái cơ bản nhất: $f[0]=0$. Xét đến tổng $1$. Có duy nhất đồng xu $1$ nhỏ hơn hoặc bằng tổng $1$, nên ta có $f[1]=f[1−v_1]+1=f[0]+1=1$. Xét đến tổng $2$. Cũng giống như tổng trước, chỉ có $1$ đổng xu không vượt quá $2$, suy ra $f[2]=f[2−v_1]+1=f[1]+1=2$. Đến tổng $3$. Lần này có hai đồng xu không vượt quá $3$ là $1$ và $3$. Nếu ta chọn đồng $1$, ta có $f[3]=f[3−v_1]+1=f[2]+1=3$; nếu ta chọn đồng $3$, ta có $f[3]=f[3−v_2]+1=f[0]+1=1$. Rõ ràng $1 ≤ 3$ nên ta chọn đồng $3$ và $f[3]=1$. Xét tiếp đến tổng $4,$ tổng $5,\ldots$ đến $11$ bằng cách như trên. Đây là lời giải cho tất cả các tổng: Tổng | Lượng xu nhỏ nhất | Xu được chọn
[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=

include using namespace std; const int N = 1e3 + 10; int f[N], v[N], n, S; // Gán f[i] = -1 nếu không thể tìm được một số đồng xu tổng bằng i int main[] { cin >> n >> S; for [int i = 1; i > v[i]; for [int i = 1; i a[i]; for [int i = 1; i > m[i].b; } sort[m + 1, m + n + 1, compare]; // Bước quy hoạch động for [int i = 1; i **Điều kiện:** $1\le L\le n\le1000, 1\le U\le10^9$ và $1\le a_1, a_2,\dots, a_n\le10^9$. Dãy con đổi dấu $a_{i_1},a_{i_2},\ldots, a_{i_k}$ phải thoả mãn các điều kiện sau: - $A_{i_1} < A_{i_2} > A_{i_3} A_{i_2} < A_{i_3} >\ldots$ - Các chỉ số phải cách nhau ít nhất $L: i_2 - i_1 \ge L, i_3 - i_2 \ge L, \ldots$ - Chênh lệch giữa 2 phần tử liên tiếp không vượt quá $U:$ $|A_{i1} - A_{i2}| \le U,$ $|A_{i2} - A_{i3}| \le U, \ldots$ **Hướng dẫn**: Gọi $Q[i]$ là số phần tử của dãy con đổi dấu có phần tử cuối cùng là $a_i$ và phần tử cuối cùng lớn hơn phần tử đứng trước. Tương tự, $P[i]$ là số phần tử của dãy con đổi dấu có phần tử cuối cùng là $a_i$ và phần tử cuối cùng nhỏ hơn phần tử đứng trước. Ta dễ dàng suy ra: - $Q[i] = \max [1, P[j] + 1]$, với mọi $j$ thỏa mãn: $j \le i-L$ và $A_i - U \le A_j < A_i$. - $P[i] = \max [1, Q[j] + 1]$, với mọi $j$ thỏa mãn: $j \le i-L$ và $A_i < A_j \le A_i + U$. ```cpp=

include using namespace std; const int N = 1e3 + 10; int a[N], P[N], Q[N], n, U, L; int main[] { cin >> n >> U >> L; for [int i = 1; i > a[i]; for [int i = 1; i *Ví dụ dãy số `1 2 3 4 5 2 1` là 1 dãy WAVIO độ dài 7. Cho dãy $a$ gồm $n$ số nguyên, hãy chỉ ra một dãy con Wavio có độ dài lớn nhất trích ra từ dãy đó.* > **Điều kiện:** $1\le n\le 1000$ và $1\le a_1,a_2,\ldots,a_n\le10^9$ với mọi $i=1;2;\ldots;n$. **Hướng dẫn**: Ta sẽ quy hoạch động theo phần tử $a_m$ của dãy WAVIO như sau: * $Q[i]$ là độ dài của dãy con tăng dần dài nhất kết thúc ở $i$ * $P[i]$ là độ dài của dãy con giảm dần dài nhất bắt đầu ở $i$ Khi đó, trong các dãy WAVIO có $i$ là đỉnh thì dãy dài nhất sẽ có độ dài $Q[i]+P[i]-1$. Đến đây, chỉ cần tìm $\max[Q[i]+P[i]-1]$. # Intermediate Ở mục này, chúng ta sẽ làm quen với QHĐ hai chiều, ta bắt đầu bằng ví dụ sau: > *Cho một bảng ô vuông gồm $m$ hàng và $n$ cột. Kí hiệu $[i, j]$ là ô ở hàng $i$, cột $j$. Giả sử $[i, j]$ có $a_{i,j}$ quả táo. Bạn An muốn đi từ $[1, 1]$ đến $[m, n]$. Ở mỗi bước, An đi sang phải hoặc xuống dưới đúng một ô. Khi An ở ô $[i, j]$, An có thể lấy hết các quả táo ở ô đó. Tính số quả táo nhiều nhất mà An có thể lấy được.* > **Điều kiện:** $1\le mn\le10^6$ và $1\le a_{i, j}\le 10^9$ với mọi $i,j$. ![Minh họa][//i.imgur.com/AnC2FKV.png] **Ý tưởng:** Bài toán này cũng tương tự như các ví dụ trước. Đầu tiên, trạng thái của bài toán chính là số quả táo nhiều nhất An có thể lấy khi đi từ ô $[1,1]$ đến ô $[i,j]$, gọi là $f[i][j]$. Đầu tiên ta khởi tạo $f[1][1] = a_{1,1}$. ![Minh họa][//raw.githubusercontent.com/Ryu204/Picture/main/table2.png]> Với mọi $i,j\ge 2$, để đi từ $[1, 1]$ đến $[i, j]$ An có hai lựa chọn: đi qua $[i - 1, j]$ hoặc đi qua $[i, j - 1]$. An sẽ chọn đường đi thu được nhiều táo nhất, do đó $f[i][j] = a_{i, j} + \max[f[i][j - 1], f[i - 1][j]]$. ![Minh họa][//i.imgur.com/2LEYFzi.png] ```cpp=

include using namespace std; const int N = 1e3 + 10; int m, n, a[N][N]; long long f[N][N]; int main[] { cin >> n >> m; for [int i = 1; i a[i][j]; for [int i = 1; i n; int t = 0; for [int i = 1; i > a[i]; t += a[i]; } for [int i = 0; i