Hướng dẫn giải của Xâu con chung dài nhất
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm độ dài của xâu con chung dài nhất (Longest Common Subsequence - LCS) giữa hai xâu A và B. Xâu con được định nghĩa là xâu có thể thu được bằng cách xóa một số ký tự (có thể không xóa ký tự nào hoặc xóa tất cả) từ xâu ban đầu, không nhất thiết phải xóa liên tiếp. Ví dụ, "ace" là xâu con của "abcde". Với hai xâu A và B có độ dài tối đa 2000, ta cần tìm độ dài lớn nhất của xâu C sao cho C là xâu con của cả A và B.
Các cách tiếp cận
Cách Quy hoạch động (Dynamic Programming)
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
char a[2005], b[2005];
fgets(a, 2005, stdin);
a[strcspn(a, "\n")] = '\0';
fgets(b, 2005, stdin);
b[strcspn(b, "\n")] = '\0';
int m = strlen(a);
int n = strlen(b);
// dp[i][j] lưu độ dài LCS của a[0...i-1] và b[0...j-1]
// Kích thước m+1 x n+1 để xử lý trường hợp cơ sở
int dp[2005][2005];
// Khởi tạo cơ sở: LCS với xâu rỗng là 0
for (int i = 0; i <= m; i++) dp[i][0] = 0;
for (int j = 0; j <= n; j++) dp[0][j] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a[i-1] == b[j-1]) {
// Nếu ký tự cuối khớp, tăng độ dài LCS thêm 1
dp[i][j] = dp[i-1][j-1] + 1;
} else {
// Nếu không khớp, lấy giá trị lớn hơn từ:
// LCS của a[0...i-2] và b[0...j-1] HOẶC a[0...i-1] và b[0...j-2]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
printf("%d\n", dp[m][n]);
return 0;
}
- Time Complexity: O(m * n), với m, n là độ dài hai xâu (tối đa ~4*10^6)
- Space Complexity: O(m * n) (có thể tối ưu xuống O(min(m, n)))
Đây là phương pháp chuẩn để giải bài toán LCS. Ta xây dựng bảng quy hoạch động dp[m+1][n+1] trong đó dp[i][j] biểu diễn độ dài LCS của hai xâu con a[0...i-1] và b[0...j-1].
Công thức truy hồi:
- Nếu i = 0 hoặc j = 0: dp[i][j] = 0 (trường hợp cơ sở)
- Nếu a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1
- Nếu a[i-1] != b[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Ta điền bảng theo thứ tự từ trên xuống, từ trái sang phải. Giá trị dp[m][n] chính là kết quả cần tìm.
Cách Quy hoạch động với mảng 1 chiều (Space Optimization)
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int main() {
char a[2005], b[2005];
fgets(a, 2005, stdin);
a[strcspn(a, "\n")] = '\0';
fgets(b, 2005, stdin);
b[strcspn(b, "\n")] = '\0';
int m = strlen(a);
int n = strlen(b);
// Chỉ cần lưu hàng trước đó và hàng hiện tại
int dp[2][2005];
// Khởi tạo hàng 0
for (int j = 0; j <= n; j++) dp[0][j] = 0;
for (int i = 1; i <= m; i++) {
dp[1][0] = 0; // Cột đầu tiên của hàng hiện tại
for (int j = 1; j <= n; j++) {
if (a[i-1] == b[j-1]) {
dp[1][j] = dp[0][j-1] + 1;
} else {
dp[1][j] = max(dp[0][j], dp[1][j-1]);
}
}
// Sao chép hàng hiện tại vào hàng trước cho lần lặp tiếp theo
for (int j = 0; j <= n; j++) {
dp[0][j] = dp[1][j];
}
}
printf("%d\n", dp[0][n]);
return 0;
}
- Time Complexity: O(m * n)
- Space Complexity: O(n)
Khi tính dp[i][j], ta chỉ cần dp[i-1][...] (hàng trước) và dp[i][...j-1] (phần đã tính của hàng hiện tại). Do đó, ta có thể tối ưu không gian bằng cách chỉ lưu 2 hàng liên tiếp thay vì toàn bộ bảng. Hàng 'cũ' (i-1) lưu ở dp[0], hàng 'mới' (i) lưu ở dp[1]. Sau mỗi dòng i, ta cập nhật dp[0] = dp[1].
Cách Đệ quy với Memorization
#include <stdio.h>
#include <string.h>
char a[2005], b[2005];
int memo[2005][2005];
int m, n;
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(int i, int j) {
// Trường hợp cơ sở: một trong hai xâu hết ký tự
if (i == 0 || j == 0) return 0;
// Nếu đã tính toán rồi thì trả về ngay
if (memo[i][j] != -1) return memo[i][j];
// Nếu ký tự cuối khớp
if (a[i-1] == b[j-1]) {
return memo[i][j] = 1 + lcs(i-1, j-1);
}
// Nếu không khớp, thử bỏ qua ký tự từ a hoặc từ b
return memo[i][j] = max(lcs(i-1, j), lcs(i, j-1));
}
int main() {
fgets(a, 2005, stdin);
a[strcspn(a, "\n")] = '\0';
fgets(b, 2005, stdin);
b[strcspn(b, "\n")] = '\0';
m = strlen(a);
n = strlen(b);
// Khởi tạo mảng memo với -1
memset(memo, -1, sizeof(memo));
printf("%d\n", lcs(m, n));
return 0;
}
- Time Complexity: O(m * n)
- Space Complexity: O(m * n) (cho memo và stack)
Phương pháp này sử dụng đệ quy trực tiếp dựa trên định nghĩa của LCS. Hàm lcs(i, j) tính độ dài LCS của a[0...i-1] và b[0...j-1]. Memorization (mảng memo) được sử dụng để lưu kết quả của các bài toán con đã tính để tránh tính toán lại, loại bỏ nhánh cây đệ quy vô hạn và đảm bảo độ phức tạp O(m*n).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(m * n), với m, n là độ dài hai xâu (tối đa ~4*10^6) | O(m * n) (có thể tối ưu xuống O(min(m, n))) | Quy hoạch động (Dynamic Programming) |
| 2 | O(m * n) | O(n) | Quy hoạch động với mảng 1 chiều (Space Optimization) |
| 3 | O(m * n) | O(m * n) (cho memo và stack) | Đệ quy với Memorization |
Bài học kinh nghiệm
- Bài toán có tính chất tối ưu con (optimal substructure): Giải pháp tối ưu cho bài toán lớn chứa các giải pháp tối ưu cho bài toán con.
- Bài toán có tính lặp lại (overlapping subproblems): Các bài toán con được giải quyết nhiều lần trong quá trình đệ quy.
- Công thức truy hồi: LCS(S1, S2) = 1 + LCS(S1[1:], S2[1:]) nếu S1[0] == S2[0], ngược lại = max(LCS(S1[1:], S2), LCS(S1, S2[1:]))
Lỗi thường gặp
- Lỗi truy cập mảng: Khi dùng quy hoạch động mảng 2 chiều, chú ý chỉ số i, j tương ứng với độ dài xâu. Đa số code dùng dp[i][j] cho xâu con kết thúc trước chỉ số i, j.
- Quên xử lý ký tự newline '\n' khi dùng fgets. Nên dùng strcspn để loại bỏ hoặc dùng scanf với %s (nhưng scanf sẽ dừng ở khoảng trắng).
- Sử dụng mảng quá nhỏ nếu khai báo cố định 2000, nhưng đề bài nói tối đa 2000, nên khai báo 2005 hoặc 2001 để an toàn.
Bình luận