Series quy hoạch động sẽ đi từ các ví dụ cơ bản đến nâng cao, quy hoạch động 1 chiều, 2 chiều. So sánh và đánh giá hai cách tiếp cận, để từ đó giúp các bạn có cái nhìn tổng quan về Quy hoạch động, hình thành tư duy, lối suy nghĩ khi gặp các bài toán về quy hoạch động.
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. Truy vết trong quy hoạch động sử dụng for
Các bài toán giải quyết bằng Quy hoạch động sử dụng vòng lặp for với cách tiếp cận Bottom-up, thứ tự thực hiện tính toán các bài toán sẽ là: Tính trước các bài toán con, rồi sau đó sử dụng kết quả của những bài toán này để tính lên cho các bài toán lớn hơn.
Ý tưởng của việc truy vết kết quả như sau:
- Đầu tiên tìm ra bài toán tối ưu nhất (chính là phần “Kết quả nằm ở đâu” trong bước quy hoạch động ở phần trước), giả sử gọi là bài toán X
- Sau đó, tìm xem bài toán X được tính bởi bài toán nào? Giả sử bài toán X được tính bởi max(bài toán X1.1, bài toán X1.2) thì ta xem trong hai bài toán đó, giá trị X lớn nhất đạt được bởi bài toán X1.1 hay X1.2. Ta gọi X1 là tên của bài toán đó.
- Tương tự, từ bài toán X1, ta tìm xem X1 được tính bởi bài toán nào giống bên trên
- Lần ngược kết qủa cho đến khi gặp bài toán cơ sở
3. Bài toán Xếp hàng mua vé
Link đề bài: Xếp hàng mua vé
Yêu cầu đề bài: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.
# Một số bài toán Quy hoạch động #### Viết bài: Trần Gia Huy Dưới đây là một số bài toán sử dụng phương pháp Quy hoạch động ~~cơ bản~~ mà mình đã hoặc đã từng làm, sol có thể còn sai sót mong nhận được sự thông cảm từ bạn đọc. $-arigatou$ $gozaimasu-$ ## Bài 1: LIS - Dãy con tăng dài nhất (bản dễ). Link chấm bài: //oj.vnoi.info/problem/liq Cho mảng số nguyên $A$ gồm $n$ phần tử, hãy tìm dãy con (có thể không liên tiếp) tăng dài nhất của mảng $A$. Ví dụ: $A = 4, 3, 6, 7$ thì ta có độ dài dãy con tăng dài nhất là $3$. ### Nhận xét: - Gọi $dp[i]$ là độ dài dãy con tăng dài nhất kết thúc ở $a_i$. Ta dễ dàng nhận ra độ dài của dãy con dài nhất ta có ở trường hợp cơ sở là $1$. - Với $i < j$ mà $a_j > a_i$ thì ta có thể thêm $a_i$ vào dãy con tăng kết thúc ở $a_j$ . - Khi đó ta chỉ cần so sánh $dp[i]$ của hiện tại với $dp[j] + 1$ nghĩa là độ dài dãy con hiện tại đã tính được và độ dài dãy con vừa được tính xem cái nào lớn hơn thì ta sẽ cập nhật kết quả. - Công thức quy hoạch động: $dp[i] = max(dp[i], dp[j] + 1)$. - Độ phức tạp thời gian: $O(n^2)$. ### Code: ```cpp=1
include <bits/stdc++.h> using namespace std; int main() { int n, ans = 1; cin >> n; int a[n]; vector<int> dp(n, 1); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a[j] < a[i]) { dp[i] = max(dp[i], dp[j] + 1); ans = max(ans, dp[i]); } } } cout << ans; return 0; } ``` ## Bài 2: LIS - Dãy con tăng dài nhất (bản khó). Tuy ý tưởng này không phải DP nhưng thôi cứ note đây :v Link chấm bài: //oj.vnoi.info/problem/lis Đề tương tự như trên nhưng ta sẽ có nhiều phương pháp để tối ưu thời gian chạy thuật toán như **Chặt nhị phân**, **Fenwick tree**,... Ta khởi tạo mảng $dp$ để lưu dãy con tăng dài nhất, từ đó ta rút ra được nhận xét như sau: Ban đầu $dp[1] = a[1]$ vì dãy con tăng dài nhất đầu tiên chỉ chứa một phần tử. Tiến hành duyệt từ $a[2]$ trở đi, khi đó xảy ra 3 trường hợp: ### *Trường hợp 1:* Nếu $a[i] < dp[1]$ thì ta cập nhật $dp[1] = a[i]$ để đảm bảo rằng dãy con tăng dài nhất bắt đầu từ $a[i]$ và chỉ chứa một phần tử. ### *Trường hợp 2:* Nếu $a[i]$ lớn hơn phần tử cuối cùng đang xét ở mảng $dp$ thì ta sẽ tăng biến $ans$ lên $1$ đơn vị và gán $dp[ans] = a[i]$. Khi đó, $dp[ans]$ chính là phần tử lớn nhất trong dãy con tăng có độ dài $ans$. ### *Trường hợp 3:* Nếu $a[i]$ nằm giữa các phần tử của dãy $dp$ thì khi đó ta cần tìm vị trí chính xác của nó trong $dp$ để cập nhật. Rõ ràng nếu $a[i]$ là phần tử lớn nhất trong dãy $dp$ thì ta chỉ cần tăng $ans$ lên $1$ đơn vị và gán $dp[ans] = a[i]$ (như *trường hợp 2*). Tuy nhiên, nếu $a[i]$ không phải là phần tử lớn nhất trong $dp$ thì ta cần tìm vị trí chính xác để chèn vào sao cho dãy $dp$ vẫn duy trì tính chất tăng dần. Để làm được điều này, ta sử dụng *chặt nhị phân kết quả*. Ta tiến hành tìm vị trí $r$ sao cho $dp[r]$ là phần tử đầu tiên trong dãy $dp$ lớn hơn hoặc bằng $a[i]$, khi tìm được ta gán $dp[r] = a[i]$. ### Code cài đặt bằng Binary Search: ```cpp=1 // author : Tran Gia Huy
include "bits/stdc++.h" using namespace std;
define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
define all(x) x.begin(), x.end()
define sz(x) (int)x.size()
define TIME (1.0 * clock() / CLOCKS_PER_SEC)
define maxn 100005 int n, a[maxn], ans = 1; vector<int> dp(maxn, 0); void OnePunchAC() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; dp[1] = a[1]; for (int i = 2; i <= n; i++) { if (a[i] < dp[1]) dp[1] = a[i]; else if (a[i] > dp[ans]) dp[ans] = a[i]; else { int l = 0, r = ans + 1; while (r - l > 1) { int m = (l + r) >> 1; if (dp[m] >= a[i]) r = m; else l = m; } dp[r] = a[i]; } } cout << ans << '\n'; //for (int i = 1; i <= n; i) cout << dp[i] << " "; // Truy vet } int main() { fastIO int tt = 1; //cin >> tt; while(tt--) OnePunchAC(); cerr << '\n' << "Times: " << TIME << "s." << '\n'; return 0; } ``` ### Code cài đặt bằng Fenwick Tree: ```cpp=1 /* author : Tran Gia Huy */
include <bits/stdc++.h> using namespace std;
define fast_paced ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
define all(x) x.begin(), x.end()
define sz(x) (int)x.size()
define builtin_popcount __builtin_popcountll
define fi first
define se second
define p64 pair<long long, long long>
define p32 pair<int, int>
define ll long long
define ull unsigned long long
define ldb long double
define TIME (1.0 * clock() / CLOCKS_PER_SEC)
define maxn 200005 const ldb PI = 3.1415926535897932384626433832795028841971693993751058209749445923, EPS = 1e-6; const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e9 + 9; int n, a[maxn], b[maxn], bit[maxn]; // Might I solve this issue very expeditiously? void update(int x, int v) { for (; x < maxn; x += x & -x) bit[x] = max(bit[x], v); } int get(int x) { int ans = 0; for (; x; x -= x & -x) ans = max(ans, bit[x]); return ans; } void moon() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i]; sort(b + 1, b + n + 1); for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b; int ans = 0; for (int i = 1; i <= n; i++) { int x = get(a[i]) + 1; update(a[i], x); ans = max(ans, x); } cout << ans; } int main() { fast_paced int tt = 1; //cin >> tt; while(tt--) moon(); cerr << '\n' << "Times: " << TIME << "s." << '\n'; return 0; } /** ---- NOTES ---- ------- **/ ``` ## Bài 3: Princess. Link chấm bài: Ngày xửa ngày xưa có một nàng công chúa dễ thương tên là Farida sống trong lâu đài cùng với cha, mẹ và chú của mình. Trên đường đến lâu đài có nhiều quái vật. Mỗi người trong số họ có một số tiền vàng. Mặc dù chúng là quái vật nhưng chúng sẽ không làm bạn bị thương. Thay vào đó, chúng sẽ đưa cho bạn những đồng tiền vàng, nhưng quái vật thứ $i$ chỉ đưa vàng cho bạn khi và chỉ khi bạn không lấy bất kì đồng xu nào từ quái vật thứ $i - 1$. **Dữ liệu nhập:** + Dòng đầu tiên chứa số nguyên $T$ là số lượng bộ test ($1 ≤ T ≤ 10$). + Mỗi trường hợp thử nghiệm bắt đầu bằng $N$ - số lượng quái vật ($0 ≤ N ≤ 10^4$). + Dòng tiếp theo sẽ có $N$ số $x_1, x_2, ..., x_n$ ($0 ≤ x_i ≤ 10^9$). Với $x_i$ là số đồng vàng quái vật thứ $i$ có. Quái vật được mô tả theo thứ tự họ gặp trên đường đến lâu đài. **Kết quả:** + In ra $T$ dòng, mỗi dòng là một đáp án cho một trường hợp thử nghiệm. **Sample input:** ``` 2 5 1 2 3 4 5 1 10 ``` **Sample output:** ``` 9 10 ``` ### Nhận xét: Gọi $dp[i]$ là số lượng đồng xu nhiều nhất khi lấy đến quái vật thứ $i$. Dễ dàng nhận ra trường hợp $n = 0$ nghĩa là không có con quái vật nào hết thì đồng nghĩa với việc số lượng đồng xu nhiều nhất ta có thể đạt được là $= 0$. > <span style="color:black">$dp[0] = 0$</span> > [color=
138ec6] Với $n > 0$ thì ta duyệt từ $i = 2$, khi đó có 2 trường hợp: ### *Trường hợp 1:* Ta sẽ lấy đồng xu của quái vật thứ $i - 1$, thì ta sẽ không lấy được xu của quái vật thứ $i$. ### *Trường hợp 2:* Ta sẽ không lấy xu của quái vật thứ $i - 1$ thì khi đó ta sẽ lấy đồng xu của con quái vật thứ $i$ đưa cho ta là $x[i]$. > <span style="color:black">Công thức quy hoạch động: $dp[i] = max(dp[i - 1], dp[i - 2] + x[i])$</span> > [color=
138ec6] ### Code: ```cpp=1 /* author : Tran Gia Huy */
include <bits/stdc++.h> using namespace std;
define fast_paced ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
define all(x) x.begin(), x.end()
define sz(x) (int)x.size()
define ll long long
define TIME (1.0 * clock() / CLOCKS_PER_SEC) const ldb PI = 3.1415926535897932384626433832795028841971693993751058209749445923, EPS = 1e-6; const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e9 + 9; // Might I solve this issue very expeditiously? void moon() { int n; cin >> n; ll dp[n + 1], x[n + 1]; memset(dp, 0, sizeof dp); for (int i = 1; i <= n; i++) cin >> x[i]; dp[0] = 0; // Trường hợp cơ sở if (n >= 1) { dp[1] = x[1]; } for (int i = 2; i <= n; i++) { dp[i] = max(dp[i - 1], dp[i - 2] + x[i]); } cout << dp[n] << '\n'; } int main() { fast_paced int tt = 1; cin >> tt; while(tt--) moon(); cerr << '\n' << "Times: " << TIME << "s." << '\n'; return 0; } ``` ## Bài 4: Chuyển tin (HSG 12 Bến Tre 2021 - 2022). Link chấm bài : Cần chuyển hết $n$ gói tin trên một mạng gồm $m$ kênh truyền. Biết chi phí chuyển $i$ gói trên kênh $j$ là $C(i, j)$ ($1 ≤ C(i, j) ≤ 10000$). **Yêu cầu:** cho biết một phương án chuyển gói tin với chi phí thấp nhất. **Dữ liệu:** Dòng đầu tiên gồm hai số $n$ và $m$ ($1 < n, m ≤ 10000$). Dòng thứ $i$ trong $n$ dòng tiếp theo, mỗi dòng gồm dãy $m$ số nguyên dương $C_1, C_2, ..., C_m$ trong đó $C_j$ là chi phí chuyển $i$ gói tin trên kênh $j$. **Kết quả:** Dòng đầu tiên: tổng chi phí thấp nhất theo phương án tìm được. Dòng thứ $j$ trong $m$ dòng tiếp theo là số lượng gói tin chuyển trên kênh $j$. **Sample input:** ``` 5 4 31 10 1 1 1 31 12 13 4 10 31 1 6 1 20 19 10 5 10 10 ``` **Sample output:** ``` 2 0 4 1 0 ``` **Giải thích:** với $n = 5$ gói tin, $m = 4$ kênh và chi phí $C(i, j)$ cho trước, trong đó $i$ là chỉ số dòng (số gói tin), $j$ là chỉ số cột (kênh) thì cách chuyển sau đây cho kết quả chi phí thấp nhất là $2$. | Kênh | Số gói tin | Chi phí | |::|:--:|:---:| | 1 | 0 | 0 | | 2 | 4 | 1 | | 3 | 1 | 1 | | 4 | 0 | 0 | > $31$ $10$ <span style="color:red">$1$</span> $1$ $1$ $31$ $12$ $13$ $4$ $10$ $31$ $1$ $6$ <span style="color:red">$1$</span> $20$ $19$ $10$ $5$ $10$ $10$ > [color=
138ec6] ### Nhận xét: Gọi $dp[i][j]$ là chi phí nhỏ nhất để tạo ra $i$ gói sử dụng kênh $j$, nên đáp án là $dp[n][m]$. Giả sử tại kênh $j$ phải sử dụng $x$ gói thì ta sẽ duyệt for để tính số gói tại kênh $j$. Vậy thì trạng thái lúc này đang là $x$ gói tại kênh $j$ nên ta dễ dàng suy ra được trạng thái trước đó sẽ là $i - x$ gói tại kênh $j - 1$. Công thức quy hoạch động: $dp[i][j] = min(dp[i][j], dp[i - x][j - 1] + a[x][j])$. Ở bài này cần phải truy vết nên ta sẽ khởi tạo một mảng 2 chiều và 1 vector để làm điều đó. Ta khởi tạo biến $x$ và gán cho nó bằng vết cuối cùng sau khi quy hoạch động, và ta sẽ cập nhật $res$$[$kênh thứ $j$$]$ $= x$, nghĩa là lưu số gói đã dùng tại kênh $j$ và cứ như thế ta truy vết tiếp. ### Code: ```cpp=1 // author : Tran Gia Huy
include "bits/stdc++.h" using namespace std;
define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
define all(x) x.begin(), x.end()
define sz(x) (int)x.size()
define pb push_back
define pf push_front
define ll long long
define TIME (1.0 * clock() / CLOCKS_PER_SEC) int n, m; int a[101][101], dp[101][101], ans[101][101]; vector<int> res(101); void truyvet(int i, int j) { if(j == 0) return; int x = ans[i][j]; res[j] = x; truyvet(i - x, j - 1); } void solve() { memset(dp, 0, sizeof dp); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; dp[i][j] = 1e9; } } for (int i = 1; i <= n; i++) dp[i][1] = a[i][1]; for (int i = 1; i <= n; i++) { for (int j = 2; j <= m; j++) { for (int x = 0; x <= i; x++) { if (dp[i][j] > dp[i - x][j - 1] + a[x][j]) { dp[i][j] = dp[i - x][j - 1] + a[x][j]; ans[i][j] = x; } } } } cout << dp[n][m] << '\n'; truyvet(n, m); for (int i = 1; i <= m; i++) cout << res[i] << '\n'; } int main() { fastIO int t = 1; //cin >> t; while(t--) solve(); cerr << "Times: " << TIME << "s." << endl; return 0; } ``` ## Bài 5: