Chuyên đề cơ bản 3: Quy hoạch động kinh điển trong C++ và Python: dãy con chung dài nhất, sửa xâu, QHĐ trên lưới, đếm cách đổi tiền, chia đoạn
Lời mở đầu
Ở bài 19 em đã làm quen với quy hoạch động qua Fibonacci, đếm đường đi trên lưới, cái túi 0/1, dãy con tăng dài nhất và đổi tiền. Đó là phần nhập môn: mỗi bài một công thức. Nhưng khi vào phòng thi, đề không bao giờ ghi “bài này là cái túi”. Em phải tự nhận ra một bài về hai xâu chính là LCS trá hình, một bài robot đi trên bản đồ thật ra là QHĐ trên lưới, hay một bài đếm số cách leo cầu thang chính là bài đổi tiền với vòng lặp đảo ngược.
Chuyên đề này gom lại những dạng kinh điển hay gặp nhất sau bài 19: dãy con chung dài nhất, khoảng cách sửa xâu, lưới có ô cấm và đi 3 hướng, cái túi không giới hạn, đếm cách đổi tiền (và cái bẫy thứ tự vòng lặp nổi tiếng), chia dãy thành đoạn. Nếu em quên đệ quy có nhớ, hãy xem lại bài 15, vì mọi công thức dưới đây đều có thể viết thành hàm đệ quy trước rồi mới chuyển sang vòng lặp. Phần truy vết tổng quát, QHĐ trên đoạn, bitmask và chữ số sẽ học ở bài 27.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Dãy con chung dài nhất (LCS)
Bài toán. Cho hai xâu $s$ (dài $n$) và $t$ (dài $m$). Một xâu con (dãy con) là xâu nhận được khi xoá đi một số ký tự, giữ nguyên thứ tự các ký tự còn lại, không cần liên tiếp. Tìm xâu dài nhất vừa là xâu con của $s$ vừa là xâu con của $t$. Ví dụ $s$ = ABCBDAB, $t$ = BDCABA có LCS dài 4, chẳng hạn BCBA.
Hình dung LCS như việc nối dây giữa hai xâu: mỗi sợi dây nối hai ký tự giống nhau, và các sợi dây không được cắt nhau (vì phải giữ thứ tự). LCS là cách nối được nhiều dây nhất.
Hình 1. LCS = BCBA: bốn sợi dây xanh lá nối các ký tự giống nhau, không sợi nào cắt nhau. Các ký tự xám bị bỏ qua.
Trạng thái. Gọi $dp[i][j]$ là độ dài LCS của $i$ ký tự đầu của $s$ và $j$ ký tự đầu của $t$. Đáp án là $dp[n][m]$. Hàng 0 và cột 0 ứng với xâu rỗng nên bằng 0. Công thức: nhìn hai ký tự cuối $s_i$ và $t_j$ (trong code là s[i-1], t[j-1] vì đánh số từ 0):
- Nếu $s_i = t_j$: nối luôn một sợi dây giữa hai ký tự này, phần còn lại là bài toán nhỏ hơn: $dp[i][j] = dp[i-1][j-1] + 1$.
- Nếu $s_i \ne t_j$: hai ký tự này không thể cùng được nối (nếu cả hai đều có dây thì hai dây phải nối với nhau, vô lý). Vậy bỏ $s_i$ hoặc bỏ $t_j$: $dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1])$.
Mỗi ô chỉ cần ô trên, ô trái và ô chéo trên trái, nên duyệt hàng tăng, cột tăng là đủ. Độ phức tạp $O(nm)$ cả thời gian lẫn bộ nhớ.
// dp[i][j]: đáp án cho s[0..i-1] và t[0..j-1]
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++){
if(i == 0 || j == 0){ dp[i][j] = cơ sở; continue; }
if(s[i - 1] == t[j - 1]) dp[i][j] = ... dp[i - 1][j - 1] ...;
else dp[i][j] = kết hợp(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}Truy vết. Muốn in ra chính xâu LCS, khi điền mỗi ô ta để ý nó lấy giá trị từ đâu: ↖ (hai ký tự khớp), ↑ (bỏ $s_i$) hay ← (bỏ $t_j$). Xong bảng, đứng ở góc dưới phải và đi ngược theo mũi tên; mỗi lần đi chéo ↖ là gom được một ký tự. Vì đi từ cuối về đầu nên phải đảo xâu gom được. Em bấm từng bước để xem cả hai pha, rồi thử đổi hai xâu khác:
| ∅ | B | D | C | A | B | A | |
|---|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | ↑0 | ↑0 | ↑0 | ↖1 | ←1 | ↖1 |
| B | 0 | ↖1 | ←1 | ←1 | ↑1 | ↖2 | ←2 |
| C | 0 | ↑1 | ↑1 | ↖2 | ←2 | ↑2 | ↑2 |
| B | 0 | ↖1 | ↑1 | ↑2 | ↑2 | ↖3 | ←3 |
| D | 0 | ↑1 | ↖2 | ↑2 | ↑2 | ↑3 | ↑3 |
| A | 0 | ↑1 | ↑2 | ↑2 | ↖3 | ↑3 | ↖4 |
| B | 0 | ↖1 | ↑2 | ↑2 | ↑3 | ↖4 | ↑4 |
Bảng 1. Bảng LCS của s = ABCBDAB (hàng) và t = BDCABA (cột), mỗi ô ghi mũi tên và giá trị. Ô xanh lá là đường truy vết từ góc dưới phải; bốn lần đi chéo ↖ gom được A, B, C, B, đảo lại thành BCBA, dp = 4.
Xem code C++ / Python: xâu con chung dài nhất và in ra một xâu LCS (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int main(){
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; // khớp: đi chéo
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // bỏ một ký tự
}
string res = "";
int i = n, j = m;
while(i > 0 && j > 0){ // truy vết từ góc dưới phải
if(s[i - 1] == t[j - 1]){ res += s[i - 1]; i--; j--; }
else if(dp[i - 1][j] >= dp[i][j - 1]) i--; // mũi tên ↑
else j--; // mũi tên ←
}
reverse(res.begin(), res.end()); // gom ngược nên phải đảo lại
cout << dp[n][m] << "\n" << res;
return 0;
}import sys
s, t = sys.stdin.read().split()
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # khớp: đi chéo
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # bỏ một ký tự
res = []
i, j = n, m
while i > 0 and j > 0: # truy vết từ góc dưới phải
if s[i - 1] == t[j - 1]:
res.append(s[i - 1]); i -= 1; j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1 # mũi tên ↑
else:
j -= 1 # mũi tên ←
print(dp[n][m])
print(''.join(reversed(res))) # gom ngược nên phải đảo lạiMột mẹo đáng nhớ: nếu $s$ và $t$ là hai hoán vị của $1..n$ thì LCS của chúng bằng dãy con tăng dài nhất (bài 19) của dãy “vị trí trong $t$ của từng phần tử $s$”. Nhờ đó bài $n = 10^5$ (bảng $O(n^2)$ không chạy nổi) vẫn giải được trong $O(n \log n)$.
Phần 2Khoảng cách sửa xâu (edit distance)
Bài toán. Cho xâu $s$ và $t$. Mỗi phép biến đổi là một trong ba thao tác trên $s$: chèn một ký tự, xoá một ký tự, sửa một ký tự thành ký tự khác. Hỏi cần ít nhất bao nhiêu phép để biến $s$ thành $t$? Con số này gọi là khoảng cách Levenshtein; trình soạn thảo dùng nó để gợi ý sửa lỗi chính tả, và nó cũng là “họ hàng” gần của LCS.
Trạng thái: $dp[i][j]$ = số phép ít nhất để biến $i$ ký tự đầu của $s$ thành $j$ ký tự đầu của $t$. Xét ký tự cuối:
- $s_i = t_j$: không cần làm gì với hai ký tự này, $dp[i][j] = dp[i-1][j-1]$.
- $s_i \ne t_j$: thao tác cuối cùng phải xử lý chúng bằng một trong ba cách, cộng 1 phép:
| Thao tác cuối | Ý nghĩa | Đi từ ô | Hướng trong bảng |
|---|---|---|---|
| Sửa $s_i$ thành $t_j$ | sau đó hai ký tự cuối khớp nhau | $dp[i-1][j-1] + 1$ | ↖ chéo |
| Xoá $s_i$ | còn phải biến $s_{1..i-1}$ thành $t_{1..j}$ | $dp[i-1][j] + 1$ | ↑ trên |
| Chèn $t_j$ vào cuối $s$ | còn phải biến $s_{1..i}$ thành $t_{1..j-1}$ | $dp[i][j-1] + 1$ | ← trái |
Bảng 2. Ba lựa chọn khi hai ký tự cuối khác nhau: $dp[i][j] = 1 + \min$ của ba ô.
Cơ sở khác LCS: $dp[i][0] = i$ (xoá hết $i$ ký tự) và $dp[0][j] = j$ (chèn đủ $j$ ký tự). Quên cơ sở này, để hàng 0 và cột 0 bằng 0 như LCS, là lỗi rất hay gặp. Ví dụ biến SUNDAY thành SATURDAY cần 3 phép: chèn A, chèn T, sửa N thành R.
| ∅ | S | A | T | U | R | D | A | Y | |
|---|---|---|---|---|---|---|---|---|---|
| ∅ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| S | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| U | 2 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 |
| N | 3 | 2 | 2 | 2 | 3 | 3 | 4 | 5 | 6 |
| D | 4 | 3 | 3 | 3 | 3 | 4 | 3 | 4 | 5 |
| A | 5 | 4 | 3 | 4 | 4 | 4 | 4 | 3 | 4 |
| Y | 6 | 5 | 4 | 4 | 5 | 5 | 5 | 4 | 3 |
Bảng 3. Bảng sửa xâu SUNDAY (hàng) → SATURDAY (cột). Ô xanh lá là những chỗ hai ký tự khớp (chép ô chéo, không tốn phép). Đáp án ở góc dưới phải = 3.
Em chạy tay từng ô với hai xâu ngắn. Để ý ở mỗi ô khác nhau, khung chạy tay cho biết lựa chọn nào (sửa, xoá hay chèn) cho giá trị nhỏ nhất:
Xem code C++ / Python: khoảng cách sửa xâu (chèn, xoá, sửa) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main(){
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
for(int i = 0; i <= n; i++) dp[i][0] = i;
for(int j = 0; j <= m; j++) dp[0][j] = j;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
}
}
cout << dp[n][m];
return 0;
}import sys
s, t = sys.stdin.read().split()
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i # xoá hết i ký tự
for j in range(m + 1):
dp[0][j] = j # chèn đủ j ký tự
for i in range(1, n + 1):
for j in range(1, m + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # sửa
dp[i - 1][j], # xoá s[i-1]
dp[i][j - 1]) # chèn t[j-1]
print(dp[n][m])2. Mỗi thao tác có chi phí khác nhau: thay số 1 bằng chi phí tương ứng, kể cả ở hàng 0 và cột 0 (bài tập 6).
3. Xâu dài $5000$: bảng
int $5001 \times 5001$ tốn khoảng 100 MB. Hàng $i$ chỉ dùng hàng $i - 1$, nên giữ hai hàng là đủ (code Python ở bài tập 2, 6 làm đúng như vậy).Phần 3QHĐ trên lưới: ô cấm và đi 3 hướng
Bài 19 đã đếm số đường đi trên lưới khi robot chỉ đi sang phải hoặc xuống dưới. Công thức quen thuộc với bài tổng lớn nhất: $dp[i][j] = a[i][j] + \max(dp[i-1][j],\ dp[i][j-1])$. Đề thi thật hay thêm hai “gia vị”: ô cấm và hướng đi khác.
Ô cấm. Ô cấm không thể đứng, nên dp của nó phải mang nghĩa “không tới được”. Với bài đếm số đường: gán 0 là xong, vì 0 cách cộng vào đâu cũng không đổi. Với bài max: không được gán 0 (0 có thể lớn hơn một đường thật có tổng âm!), mà phải gán một số rất nhỏ $-\infty$ (ví dụ LLONG_MIN / 4, chia 4 để cộng thêm không bị tràn), và khi lấy max từ các ô trước cần kiểm tra “có ô nào tới được không”. Nếu ô đích vẫn là $-\infty$ thì in $-1$.
Đi 3 hướng. Bài toán: robot xuất phát ở ô bất kỳ của cột đầu, mỗi bước sang cột bên phải theo một trong ba hướng: chéo lên, ngang, chéo xuống. Kết thúc ở ô bất kỳ của cột cuối. Tìm tổng lớn nhất. Ô $(i, j)$ chỉ có thể tới từ $(i-1, j-1)$, $(i, j-1)$, $(i+1, j-1)$:
$dp[i][j] = a[i][j] + \max\big(dp[i-1][j-1],\ dp[i][j-1],\ dp[i+1][j-1]\big), \qquad dp[i][0] = a[i][0].$
Hình 2. Ba ô có thể đi tới $(i, j)$ đều nằm ở cột $j - 1$. Thứ tự tính đúng là theo từng cột.
Đây là chỗ nhiều bạn mất điểm: theo thói quen viết for i ở ngoài, for j ở trong. Khi đó lúc tính $(i, j)$, ô $(i+1, j-1)$ thuộc hàng chưa duyệt tới nên vẫn bằng 0, chương trình chạy êm mà ra kết quả sai. Quy tắc chung: ô nào được dùng thì phải tính trước. Mọi mũi tên đều đi từ cột trái sang cột phải, nên vòng ngoài là cột. Em xem mô phỏng điền bảng theo từng cột, có ô cấm:
Với lưới mặc định trong mô phỏng, đường tốt nhất là 5 → 6 → 4 → 9 → 5 với tổng 29: xuất phát ở hàng cuối, đi chéo lên hai lần, đi ngang, rồi chéo lên. Code dưới đây đọc lưới với $-1$ là ô cấm (các ô khác từ 0 trở lên) và in $-1$ nếu không có đường:
Xem code C++ / Python: đường đi tổng lớn nhất trên lưới 3 hướng có ô cấm (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long NEG = LLONG_MIN / 4; // "âm vô cùng": không tới được
long long a[1005][1005], dp[1005][1005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++) cin >> a[i][j]; // -1 là ô cấm
for(int i = 0; i < n; i++) dp[i][0] = (a[i][0] == -1) ? NEG : a[i][0];
for(int j = 1; j < m; j++) // vòng ngoài: CỘT
for(int i = 0; i < n; i++){ // vòng trong: hàng
dp[i][j] = NEG;
if(a[i][j] == -1) continue;
long long best = NEG;
for(int d = -1; d <= 1; d++){ // 3 ô ở cột trước
int p = i + d;
if(p >= 0 && p < n) best = max(best, dp[p][j - 1]);
}
if(best != NEG) dp[i][j] = best + a[i][j];
}
long long ans = NEG;
for(int i = 0; i < n; i++) ans = max(ans, dp[i][m - 1]);
cout << (ans == NEG ? -1 : ans);
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [list(map(int, data[2 + i * m: 2 + (i + 1) * m])) for i in range(n)]
NEG = float('-inf') # không tới được
dp = [[NEG] * m for _ in range(n)]
for i in range(n):
if a[i][0] != -1:
dp[i][0] = a[i][0]
for j in range(1, m): # vòng ngoài: CỘT
for i in range(n): # vòng trong: hàng
if a[i][j] == -1:
continue
best = dp[i][j - 1]
if i > 0:
best = max(best, dp[i - 1][j - 1])
if i + 1 < n:
best = max(best, dp[i + 1][j - 1])
if best != NEG:
dp[i][j] = best + a[i][j]
ans = max(dp[i][m - 1] for i in range(n))
print(-1 if ans == NEG else ans)Phần 4Cái túi không giới hạn và đếm số cách đổi tiền
Cái túi không giới hạn. Giống cái túi 0/1 ở bài 19, nhưng mỗi loại vật có vô số cái, lấy bao nhiêu cũng được. Gọi $dp[c]$ là giá trị lớn nhất khi sức chứa là $c$. Chỉ cần đổi chiều của vòng lặp sức chứa:
| Cái túi 0/1 (bài 19) | Cái túi không giới hạn | |
|---|---|---|
| Vòng lặp | for c = W down to w | for c = w to W |
| Khi đọc $dp[c - w]$ | vẫn là giá trị cũ (chưa có vật $i$) | đã là giá trị mới (có thể đã chứa vật $i$) |
| Hệ quả | mỗi vật lấy tối đa 1 lần | vật $i$ được lấy lại nhiều lần |
Bảng 4. Chỉ khác nhau ở chiều duyệt $c$. Ví dụ sức chứa 10, ba vật (nặng 3, giá 5), (nặng 4, giá 7), (nặng 5, giá 9): túi 0/1 được 16 (vật 2 và 3), túi không giới hạn được 18 (hai vật nặng 5).
Xem code C++ / Python: cái túi không giới hạn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long dp[100005]; // dp[c]: giá trị lớn nhất với sức chứa c
int main(){
int n, W;
cin >> n >> W;
for(int i = 0; i < n; i++){
int w; long long v;
cin >> w >> v;
for(int c = w; c <= W; c++) // c TĂNG dần: vật i được lấy nhiều lần
dp[c] = max(dp[c], dp[c - w] + v);
}
cout << dp[W];
return 0;
}import sys
data = sys.stdin.read().split()
n, W = int(data[0]), int(data[1])
dp = [0] * (W + 1) # dp[c]: giá trị lớn nhất với sức chứa c
for i in range(n):
w, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
for c in range(w, W + 1): # c TĂNG dần: vật i được lấy nhiều lần
if dp[c - w] + v > dp[c]:
dp[c] = dp[c - w] + v
print(dp[W])Đếm số cách đổi tiền. Có các loại xu mệnh giá $c_1, \ldots, c_k$, mỗi loại vô hạn. Hỏi có bao nhiêu cách tạo ra tổng $S$? Ở đây có hai câu hỏi khác nhau mà đề hay viết rất giống nhau:
- Tổ hợp: $1 + 2 + 2$ và $2 + 1 + 2$ là một cách (chỉ quan tâm dùng bao nhiêu xu mỗi loại). Ví dụ: đổi tiền, mua hàng.
- Chỉnh hợp: $1 + 2 + 2$ và $2 + 1 + 2$ là hai cách khác nhau (thứ tự có ý nghĩa). Ví dụ: leo cầu thang mỗi bước 1 hoặc 2 bậc, nhảy ô, ghép xâu.
Điều kỳ diệu: cả hai đều dùng đúng một dòng dp[s] += dp[s - c] với $dp[0] = 1$; chỉ khác vòng nào ở ngoài.
| Xu ở ngoài, tổng ở trong | Tổng ở ngoài, xu ở trong | |
|---|---|---|
| Code | for c in xu: | for s = 1..S: |
| Ý nghĩa dp[s] | số cách chỉ dùng các loại xu đã xét | số dãy xu (có thứ tự) có tổng s |
| Vì sao | các xu luôn xuất hiện theo thứ tự loại 1, loại 2, … nên mỗi tập xu chỉ được đếm một lần | mọi loại xu đều được thử làm xu cuối cùng của dãy |
| Đếm | tổ hợp | chỉnh hợp |
| Xu {1, 2, 5}, S = 5 | 4 cách: 5; 2+2+1; 2+1+1+1; 1+1+1+1+1 | 9 cách: 5; 2+2+1 (3 thứ tự); 2+1+1+1 (4 thứ tự); 1+1+1+1+1 |
Bảng 5. Cùng một dòng cộng, đổi thứ tự hai vòng lặp là đổi hẳn bài toán.
Em chọn hai thứ tự khác nhau trong mô phỏng để thấy cùng mệnh giá 1, 2, 5 và $S = 6$ mà một bên ra 5, một bên ra 15. Ở thứ tự “xu ngoài”, các hàng mờ phía trên cho thấy bảng sau khi xét xong từng loại xu:
Khung chạy tay dưới đây là bản tổ hợp. Để ý lúc xét xu 2: dp[4] += dp[2] mà $dp[2]$ vừa được cộng thêm cách “2” ở bước trước, nên “2 + 2” được đếm. Đó chính là lý do duyệt $s$ tăng dần cho phép dùng một loại xu nhiều lần, giống hệt cái túi không giới hạn.
Xem code C++ / Python: đếm số cách đổi tiền theo tổ hợp và theo chỉnh hợp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long comb[100005], perm[100005];
int main(){
int n, S;
cin >> n >> S;
vector<int> c(n);
for(int i = 0; i < n; i++) cin >> c[i];
comb[0] = perm[0] = 1;
// Tổ hợp (không phân biệt thứ tự): XU ở ngoài, TỔNG ở trong
for(int i = 0; i < n; i++)
for(int s = c[i]; s <= S; s++)
comb[s] = (comb[s] + comb[s - c[i]]) % MOD;
// Chỉnh hợp (có phân biệt thứ tự): TỔNG ở ngoài, XU ở trong
for(int s = 1; s <= S; s++)
for(int i = 0; i < n; i++)
if(s >= c[i]) perm[s] = (perm[s] + perm[s - c[i]]) % MOD;
cout << comb[S] << " " << perm[S];
return 0;
}import sys
MOD = 10**9 + 7
data = sys.stdin.read().split()
n, S = int(data[0]), int(data[1])
c = list(map(int, data[2:2 + n]))
comb = [1] + [0] * S
perm = [1] + [0] * S
# Tổ hợp (không phân biệt thứ tự): XU ở ngoài, TỔNG ở trong
for x in c:
for s in range(x, S + 1):
comb[s] = (comb[s] + comb[s - x]) % MOD
# Chỉnh hợp (có phân biệt thứ tự): TỔNG ở ngoài, XU ở trong
for s in range(1, S + 1):
tot = 0
for x in c:
if s >= x:
tot += perm[s - x]
perm[s] = tot % MOD
print(comb[S], perm[S])2. Quên $dp[0] = 1$: không có nó thì mọi ô đều bằng 0.
3. Tràn số: số cách tăng rất nhanh (chỉnh hợp với xu {1, 2} chính là dãy Fibonacci), nên đề thường bắt lấy dư cho $10^9 + 7$. Lấy dư ngay sau mỗi phép cộng.
Phần 5Chia dãy thành đoạn, Kadane và quy trình nhận dạng
Dạng chia đoạn. Đề: chia dãy $a_1, \ldots, a_n$ thành các đoạn liên tiếp, mỗi đoạn có một chi phí, tìm cách chia có tổng chi phí nhỏ nhất (hoặc lớn nhất). Khuôn trạng thái: $dp[i]$ = đáp án tốt nhất khi đã chia xong $i$ phần tử đầu. Đoạn cuối cùng là $a_{j+1..i}$ với một $j$ nào đó, phần trước nó đã chia tốt nhất bằng $dp[j]$:
$dp[i] = \min\limits_{0 \le j < i} \big(dp[j] + \text{chiphi}(j+1, i)\big), \qquad dp[0] = 0.$
Ví dụ. Chia dãy thành các nhóm liên tiếp, mỗi nhóm tốn một phí cố định $C$ cộng với độ chênh (lớn nhất − nhỏ nhất) trong nhóm. Nhóm ít thì chênh lệch lớn, nhóm nhiều thì tốn phí cố định. Khi duyệt $j$ giảm dần từ $i - 1$ về 0, đoạn cuối dài thêm một phần tử về bên trái, nên cập nhật max, min trong $O(1)$; tổng cộng $O(n^2)$. Với $a$ = [1, 2, 10, 11, 3, 4] và $C = 3$:
| i | a[i] | Lựa chọn tốt nhất | Tính | dp[i] |
|---|---|---|---|---|
| 1 | 1 | đoạn cuối [1] | dp[0] + 3 + (1 − 1) = 0 + 3 + 0 | 3 |
| 2 | 2 | đoạn cuối [1, 2] | dp[0] + 3 + (2 − 1) = 0 + 3 + 1 | 4 |
| 3 | 10 | đoạn cuối [10] | dp[2] + 3 + (10 − 10) = 4 + 3 + 0 | 7 |
| 4 | 11 | đoạn cuối [10, 11] | dp[2] + 3 + (11 − 10) = 4 + 3 + 1 | 8 |
| 5 | 3 | đoạn cuối [3] | dp[4] + 3 + (3 − 3) = 8 + 3 + 0 | 11 |
| 6 | 4 | đoạn cuối [3, 4] | dp[4] + 3 + (4 − 3) = 8 + 3 + 1 | 12 |
Bảng 6. Đáp án $dp[6] = 12$: ba nhóm [1, 2], [10, 11], [3, 4], mỗi nhóm tốn $3 + 1 = 4$. Gom cả dãy vào một nhóm tốn $3 + 10 = 13$, còn mỗi phần tử một nhóm tốn $6 \cdot 3 = 18$.
Xem code C++ / Python: chia dãy thành các nhóm liên tiếp với chi phí nhỏ nhất (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long a[5005], dp[5005];
int main(){
int n; long long C;
cin >> n >> C;
for(int i = 1; i <= n; i++) cin >> a[i];
dp[0] = 0; // chưa có phần tử nào: chi phí 0
for(int i = 1; i <= n; i++){
dp[i] = LLONG_MAX;
long long mx = a[i], mn = a[i];
for(int j = i - 1; j >= 0; j--){ // đoạn cuối là a[j+1..i]
mx = max(mx, a[j + 1]); mn = min(mn, a[j + 1]);
dp[i] = min(dp[i], dp[j] + C + (mx - mn));
}
}
cout << dp[n];
return 0;
}import sys
data = sys.stdin.read().split()
n, C = int(data[0]), int(data[1])
a = [0] + list(map(int, data[2:2 + n]))
dp = [0] * (n + 1) # dp[0] = 0: chưa có phần tử nào
for i in range(1, n + 1):
best = None
mx = mn = a[i]
for j in range(i - 1, -1, -1): # đoạn cuối là a[j+1..i]
x = a[j + 1]
if x > mx: mx = x
if x < mn: mn = x
v = dp[j] + C + mx - mn
if best is None or v < best:
best = v
dp[i] = best
print(dp[n])Kadane cũng là QHĐ. Tổng đoạn con lớn nhất (bài tập 5 của bài 24 giải bằng chia để trị $O(n \log n)$) có lời giải $O(n)$ rất gọn nếu đặt đúng trạng thái: $dp[i]$ = tổng lớn nhất của một đoạn kết thúc đúng tại $i$. Đoạn đó hoặc chỉ gồm $a_i$, hoặc nối tiếp đoạn tốt nhất kết thúc tại $i - 1$:
$dp[i] = \max(a_i,\ dp[i-1] + a_i), \qquad \text{đáp án} = \max_i dp[i].$
Nói cách khác: nếu đoạn trước đang có tổng âm thì nó chỉ “kéo chân”, bỏ đi và bắt đầu lại từ $a_i$. Vì $dp[i]$ chỉ dùng $dp[i-1]$ nên giữ một biến là đủ. Chữ “kết thúc tại $i$” là mẹo đặt trạng thái cực kỳ hay dùng: LIS, Kadane, bài tập 7 và 8 đều dùng nó.
Xem code C++ / Python: tổng đoạn con lớn nhất bằng thuật toán Kadane (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
long long cur = a[0], best = a[0]; // cur = dp[i]: đoạn tốt nhất KẾT THÚC tại i
for(int i = 1; i < n; i++){
cur = max(a[i], cur + a[i]); // bắt đầu lại, hoặc nối tiếp đoạn trước
best = max(best, cur);
}
cout << best;
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
cur = best = a[0] # cur = dp[i]: đoạn tốt nhất KẾT THÚC tại i
for x in a[1:]:
cur = max(x, cur + x) # bắt đầu lại, hoặc nối tiếp đoạn trước
best = max(best, cur)
print(best)Quy trình 5 bước nhận dạng. Gặp một bài lạ, em đi lần lượt qua năm câu hỏi dưới đây. Nếu trả lời được hết, bài đó gần như chắc chắn là QHĐ và em đã có luôn công thức.
| Bước | Câu hỏi | Ví dụ trả lời (đổi tiền tổ hợp) |
|---|---|---|
| 1 | Đề hỏi lớn nhất / nhỏ nhất / đếm số cách / có tồn tại không? Thử mọi cách bằng quay lui có quá chậm không? | đếm số cách tạo tổng S; quay lui là hàm mũ |
| 2 | Lời giải có thể xây từng bước, mỗi bước một lựa chọn? Bước cuối cùng là gì? | xu cuối cùng được thêm vào |
| 3 | Sau khi bỏ bước cuối, phần còn lại có phải cùng dạng nhưng nhỏ hơn? Cần nhớ gì để mô tả nó? Đó là trạng thái. | tổng còn lại $s$, và đã xét tới loại xu nào |
| 4 | Viết công thức từ các trạng thái nhỏ hơn, chọn cơ sở và thứ tự tính sao cho ô được dùng luôn tính trước. | $dp[s] \mathrel{+}= dp[s-c]$, $dp[0] = 1$, xu ở ngoài |
| 5 | Đếm số trạng thái × số lựa chọn và so với giới hạn đề. Quá lớn thì tìm cách giảm chiều. | $k \cdot S = 10^2 \cdot 10^4 = 10^6$, rất nhanh |
Bảng 7. Năm câu hỏi giúp nhận ra và dựng một lời giải QHĐ.
| Dấu hiệu trong đề | Dạng | Trạng thái | Độ phức tạp |
|---|---|---|---|
| hai xâu / hai dãy, so khớp, giữ thứ tự, chèn xoá sửa | LCS, sửa xâu (phần 1, 2) | $dp[i][j]$ | $O(nm)$ |
| bảng, robot đi theo một số hướng cố định, không quay lại | QHĐ trên lưới (phần 3) | $dp[i][j]$ | $O(nm)$ |
| tạo tổng / sức chứa từ các loại vật, mỗi loại dùng nhiều lần | túi không giới hạn, đổi tiền (phần 4) | $dp[s]$ | $O(kS)$ |
| chia dãy thành các đoạn liên tiếp, mỗi đoạn có chi phí | chia đoạn (phần 5) | $dp[i]$ = chia xong $i$ phần tử | $O(n^2)$ hoặc $O(nK)$ |
| đoạn con / dãy con tốt nhất, điều kiện giữa hai phần tử kề nhau | Kadane, LIS | $dp[i]$ = kết thúc tại $i$ | $O(n)$, $O(n^2)$ |
Bảng 8. Bảng nhận dạng các dạng kinh điển trong chuyên đề này. Các dạng khó hơn (trên đoạn, bitmask, chữ số) có ở bài 27.
f(trạng thái) thử mọi bước cuối và gọi lại chính nó (như bài 15), thêm mảng nhớ là xong. Cách này không phải lo thứ tự tính. Sau khi chắc công thức đúng, chuyển sang vòng lặp để chạy nhanh hơn, nhất là với Python.- Frog 2 (AtCoder Educational DP Contest B) (Dễ)
- Gián Ăn (Dễ)
- Tổng đoạn con lớn nhất (Dễ)
- Xếp Hàng Mua Vé (NKTICK) (Trung bình)
- Bài toán chiếc balo 2 (BALO2) (Trung bình)
- Money Sum (Trung bình)
- Du Hành (ACM Việt Nam 10-2014) (Khá)
Bài tậpLuyện quy hoạch động kinh điển
Khu vườn là lưới $n \times m$ ($1 \le n, m \le 1000$), ô . đi được, ô # có bụi gai. Bạn Minh đứng ở góc trên trái và muốn tới góc dưới phải, mỗi bước chỉ đi sang phải hoặc xuống dưới, không bước vào ô có gai. Đếm số đường đi khác nhau, lấy dư cho $10^9 + 7$. Nếu ô xuất phát hoặc ô đích có gai thì đáp án là 0.
3 4
....
.#..
....4📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
# thì $dp = 0$ (không ai đứng được ở đó, nên cũng không truyền cách nào đi tiếp). Ô xuất phát $dp = 1$ nếu nó không có gai. Nhớ lấy dư sau mỗi phép cộng. Bản Python chỉ giữ hai hàng để tiết kiệm bộ nhớ.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int dp[1005][1005];
string g[1005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> g[i];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
if(g[i][j] == '#'){ dp[i][j] = 0; continue; } // ô cấm: 0 cách
if(i == 0 && j == 0){ dp[i][j] = 1; continue; }
long long v = 0;
if(i > 0) v += dp[i - 1][j];
if(j > 0) v += dp[i][j - 1];
dp[i][j] = v % MOD;
}
cout << dp[n - 1][m - 1];
return 0;
}import sys
MOD = 10**9 + 7
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
prev = [0] * m
for i in range(n):
cur = [0] * m
row = g[i]
for j in range(m):
if row[j] == '#': # ô cấm: 0 cách
continue
if i == 0 and j == 0:
cur[j] = 1
else:
cur[j] = (prev[j] + (cur[j - 1] if j > 0 else 0)) % MOD
prev = cur
print(prev[m - 1])Cho hai xâu $s$ và $t$ gồm chữ cái thường, độ dài không quá 1000. Mỗi thao tác được xoá một ký tự ở một trong hai xâu. Hỏi cần ít nhất bao nhiêu thao tác để hai xâu trở nên giống hệt nhau?
sea eat2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
sea và eat, LCS là ea dài 2, nên xoá $3 + 3 - 4 = 2$ ký tự (chữ s và chữ t).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main(){
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
dp[i][j] = (s[i - 1] == t[j - 1]) ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
cout << n + m - 2 * dp[n][m]; // giữ lại đúng LCS, xoá phần còn lại
return 0;
}import sys
s, t = sys.stdin.read().split()
n, m = len(s), len(t)
prev = [0] * (m + 1)
for i in range(1, n + 1):
cur = [0] * (m + 1)
a = s[i - 1]
for j in range(1, m + 1):
if a == t[j - 1]:
cur[j] = prev[j - 1] + 1
else:
cur[j] = prev[j] if prev[j] > cur[j - 1] else cur[j - 1]
prev = cur
print(n + m - 2 * prev[m]) # giữ lại đúng LCS, xoá phần còn lạiCửa hàng nhận $n$ loại tờ tiền với mệnh giá khác nhau $c_1, \ldots, c_n$ ($n \le 100$, $1 \le c_i \le 10^4$), mỗi loại có rất nhiều tờ. Hỏi có bao nhiêu cách trả đúng số tiền $S$ ($S \le 10^4$)? Hai cách chỉ khác nhau về thứ tự đưa tiền thì coi là một. In đáp án mod $10^9 + 7$.
3 5
1 2 54📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long dp[100005];
int main(){
int n, S;
cin >> n >> S;
dp[0] = 1;
for(int i = 0; i < n; i++){ // XU ở ngoài -> đếm tổ hợp
int c;
cin >> c;
for(int s = c; s <= S; s++) dp[s] = (dp[s] + dp[s - c]) % MOD;
}
cout << dp[S];
return 0;
}import sys
MOD = 10**9 + 7
data = sys.stdin.read().split()
n, S = int(data[0]), int(data[1])
dp = [1] + [0] * S
for c in map(int, data[2:2 + n]): # XU ở ngoài -> đếm tổ hợp
for s in range(c, S + 1):
dp[s] = (dp[s] + dp[s - c]) % MOD
print(dp[S])Xưởng có một thanh gỗ dài $L$ ($L \le 10^4$). Có $n$ loại khúc gỗ khách cần ($n \le 100$): loại $i$ dài $l_i$ và bán được $p_i$ đồng ($p_i \le 10^9$). Xưởng được cắt thanh gỗ thành các khúc thuộc các loại trên, mỗi loại cắt bao nhiêu khúc cũng được, phần thừa bỏ đi. Hỏi tổng số tiền lớn nhất bán được?
8 3
2 5
3 8
5 1221📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
int nên dùng long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long dp[10005];
int main(){
int L, n;
cin >> L >> n;
for(int i = 0; i < n; i++){
int l; long long p;
cin >> l >> p;
for(int c = l; c <= L; c++) // tăng dần: cắt bao nhiêu khúc loại i cũng được
dp[c] = max(dp[c], dp[c - l] + p);
}
cout << dp[L];
return 0;
}import sys
data = sys.stdin.read().split()
L, n = int(data[0]), int(data[1])
dp = [0] * (L + 1)
for i in range(n):
l, p = int(data[2 + 2 * i]), int(data[3 + 2 * i])
for c in range(l, L + 1): # tăng dần: cắt bao nhiêu khúc loại i cũng được
v = dp[c - l] + p
if v > dp[c]:
dp[c] = v
print(dp[L])Cầu thang có $n$ bậc ($n \le 10^5$), Lan đứng ở mặt đất (bậc 0) và muốn lên bậc $n$. Mỗi bước, Lan nhảy lên đúng $d$ bậc với $d$ thuộc tập $k$ số khác nhau cho trước ($k \le 10$, $1 \le d \le n$). Có $m$ bậc bị hỏng, không được đặt chân lên (bậc $n$ không hỏng). Đếm số cách lên tới bậc $n$, hai cách khác nhau nếu dãy bước nhảy khác nhau. In đáp án mod $10^9 + 7$.
Dòng 1 gồm $n, k, m$; dòng 2 gồm $k$ độ dài bước; dòng 3 gồm $m$ bậc hỏng.
5 2 1
1 2
32📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long dp[100005];
bool broken[100005];
int main(){
int n, k, m;
cin >> n >> k >> m;
vector<int> d(k);
for(auto &x : d) cin >> x;
for(int i = 0; i < m; i++){ int b; cin >> b; broken[b] = true; }
dp[0] = 1;
for(int s = 1; s <= n; s++){ // TỔNG (bậc) ở ngoài -> đếm có thứ tự
if(broken[s]) continue; // không được đặt chân: dp = 0
for(int x : d)
if(s >= x) dp[s] = (dp[s] + dp[s - x]) % MOD;
}
cout << dp[n];
return 0;
}import sys
MOD = 10**9 + 7
data = sys.stdin.read().split()
n, k, m = int(data[0]), int(data[1]), int(data[2])
d = list(map(int, data[3:3 + k]))
broken = set(map(int, data[3 + k:3 + k + m]))
dp = [0] * (n + 1)
dp[0] = 1
for s in range(1, n + 1): # TỔNG (bậc) ở ngoài -> đếm có thứ tự
if s in broken: # không được đặt chân: dp = 0
continue
tot = 0
for x in d:
if s >= x:
tot += dp[s - x]
dp[s] = tot % MOD
print(dp[n])Cho ba số $I, D, R$ ($1 \le I, D, R \le 10^6$) là chi phí của một phép chèn, xoá, sửa ký tự. Cho hai xâu $s$, $t$ (độ dài không quá 500). Tìm tổng chi phí nhỏ nhất để biến $s$ thành $t$. Dòng 1 là $I, D, R$; dòng 2 là $s$; dòng 3 là $t$.
1 1 5
abc
adc2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long dp[1005][1005];
int main(){
long long I, D, Rp;
string s, t;
cin >> I >> D >> Rp >> s >> t;
int n = s.size(), m = t.size();
for(int i = 0; i <= n; i++) dp[i][0] = i * D; // xoá hết
for(int j = 0; j <= m; j++) dp[0][j] = j * I; // chèn đủ
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
long long same = dp[i - 1][j - 1] + (s[i - 1] == t[j - 1] ? 0 : Rp);
dp[i][j] = min({same, dp[i - 1][j] + D, dp[i][j - 1] + I});
}
cout << dp[n][m];
return 0;
}import sys
data = sys.stdin.read().split()
I, D, Rp = int(data[0]), int(data[1]), int(data[2])
s, t = data[3], data[4]
n, m = len(s), len(t)
prev = [j * I for j in range(m + 1)] # hàng 0: chèn đủ j ký tự
for i in range(1, n + 1):
cur = [i * D] + [0] * m # cột 0: xoá hết i ký tự
a = s[i - 1]
for j in range(1, m + 1):
v = prev[j - 1] + (0 if a == t[j - 1] else Rp)
x = prev[j] + D
if x < v: v = x
x = cur[j - 1] + I
if x < v: v = x
cur[j] = v
prev = cur
print(prev[m])Cho dãy $n$ số nguyên ($n \le 10^5$, $|a_i| \le 10^9$). Chọn một đoạn con liên tiếp, rồi được phép bỏ đi tối đa một phần tử của đoạn (đoạn sau khi bỏ vẫn phải còn ít nhất một phần tử). Tìm tổng lớn nhất có thể.
5
1 -2 0 3 -14📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
const long long NEG = LLONG_MIN / 4;
long long f = a[0], g = NEG, best = a[0]; // f: chưa bỏ, g: đã bỏ đúng 1 phần tử
for(int i = 1; i < n; i++){
long long nf = max(a[i], f + a[i]);
long long ng = max(f, g == NEG ? NEG : g + a[i]); // bỏ a[i], hoặc đã bỏ trước đó
f = nf; g = ng;
best = max({best, f, g});
}
cout << best;
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
NEG = float('-inf')
f, g, best = a[0], NEG, a[0] # f: chưa bỏ, g: đã bỏ đúng 1 phần tử
for x in a[1:]:
f, g = max(x, f + x), max(f, g + x) # bỏ x, hoặc đã bỏ trước đó
best = max(best, f, g)
print(best)Có $n$ học sinh đứng thành hàng ($n \le 10^4$), học sinh thứ $i$ có điểm kỹ năng $a_i$ ($1 \le a_i \le 10^6$). Thầy chia hàng thành các đội gồm các bạn đứng liền nhau, mỗi đội có từ 1 đến $K$ bạn ($K \le 100$). Sau khi luyện tập, mọi bạn trong đội đều có điểm bằng điểm của bạn giỏi nhất đội. Hỏi tổng điểm cả hàng lớn nhất có thể là bao nhiêu?
7 3
1 15 7 9 2 5 1084📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long a[10005], dp[10005];
int main(){
int n, K;
cin >> n >> K;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
long long mx = 0;
for(int len = 1; len <= K && len <= i; len++){ // đội cuối là a[i-len+1..i]
mx = max(mx, a[i - len + 1]);
dp[i] = max(dp[i], dp[i - len] + mx * len);
}
}
cout << dp[n];
return 0;
}import sys
data = sys.stdin.read().split()
n, K = int(data[0]), int(data[1])
a = [0] + list(map(int, data[2:2 + n]))
dp = [0] * (n + 1)
for i in range(1, n + 1):
mx = best = 0
for ln in range(1, min(K, i) + 1): # đội cuối là a[i-ln+1..i]
x = a[i - ln + 1]
if x > mx: mx = x
v = dp[i - ln] + mx * ln
if v > best: best = v
dp[i] = best
print(dp[n])
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét