lcs.cpp
Bài toán
Cho hai xâu, tìm độ dài dãy con chung dài nhất (không nhất thiết phải là dãy liên tiếp).
Độ phức tạp
O(mn)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <string.h>
int m, n;
char a[12309];
char b[12309];
int F[2309][2309];
bool FF[2309][2309];
int max(int a, int b) { return a > b ? a : b; }
int f(int m, int n) {
if (m == 0 || n == 0) return 0;
if (FF[m][n]) return F[m][n];
int r;
if (a[m] == b[n])
r = f(m - 1, n - 1) + 1;
else
r = max(f(m - 1, n), f(m, n - 1));
FF[m][n] = true;
F[m][n] = r;
return r;
}
int main() {
scanf("%s%s", a + 1, b + 1);
m = strlen(a + 1);
n = strlen(b + 1);
printf("%d\n", f(m, n));
}
Nhận xét
Gọi f(m,n) là độ dài dãy con chung dài nhất của hai xâu a[1..m] và b[1..n]. Ta luôn có thể giả thiết là chọn các phần tử để chọn vào kết quả (tức dãy con chung) theo thứ tự từ cuối về đầu. Công thức quy hoạch động là:
f(m,n) = f(m-1,n-1)+1, nếu a[m]=b[n].
f(m,n) = max(f(m-1,n), f(m,n-1)), ngược lại
Ta có f(m,n)=0 với mọi m=0 hoặc n=0. Điều ta cần tìm là f(m,n) với m và n là độ dài của xâu a và b.
scanf("%s%s", a+1, b+1) với mục đích đánh số các chữ cái trong xâu từ 1, tức các phần tử trong xâu của ta là a[1]..a[m] và b[1]..b[n], thay vì a[0]..a[m-1], b[0]..b[n-1]
Việc quy hoạch động bằng việc gọi đệ quy giúp công thức quy hoạch động được trình bày rõ ràng, nhờ vậy mà dễ xử lý với các bài khó hơn. Với bài tập này, tất cả các phần tử trong mảng F đều được tính đến, tuy nhiên sẽ có bài tập mà rất nhiều phần tử của mảng F không được dùng đến, tiêu biểu là bài toán cái túi. Việc gọi đệ quy như thế này sẽ giảm thiểu thời gian tính toán trogn trường hợp như vậy.
Tuy nhiên quy hoạch động bằng cách gọi đệ quy yêu cầu lượng lớn stack, phụ thuộc vào độ sâu của việc gọi đệ quy. Ở bài này, độ sâu tối đa đạt được là m+n, lên đến khoảng 4000, độ sâu như vậy chưa thể làm chương trình chạy sinh lỗi, (độ sâu lớn nhất mà ta đạt được vào khoảng 50000), tuy nhiên nó làm chậm chương trình. Ta có thể hạ độ sâu của việc gọi đệ quy (giúp chương trình chạy nhanh gấp đến hai lần) bằng cách thêm vòng lặp sau trước lệnh in kết quả printf("%d\n", f(m,n));
for (i=1; i<=m; i++)
for (j=1; j<=n; j+=10)
f(i,j)
Làm như trên thì độ sâu của đệ quy giảm xuống còn 10. Chương trình chạy nhanh gấp đôi.
Mô tả
int f(int m, int n)
độ dài dãy con chung dài nhất của xâu a[1..m] và b[1..n].
int F[i][j]
mảng để lưu các giá trị của f(i,j). F[i][j] chỉ được xác định nếu FF[i][j]=true. Trong các trường hợp khác, giá trị của F[i][j] không xác định.
bool FF[i][j]
FF[i][j]=true nếu hàm f(i,j) đã từng được gọi. Khi FF[i][j]=true thì phải đảm bảo F[i][j] đã được gán.
Các lỗi thường gặp
Runtime error
- Không xét trường hợp đặc biệt : if (m==0 || n==0) return 0;
- Kích thước mảng F và FF quá bé.
Time limit exceeded
- Không lưu giá trị vào mảng F hoặc chưa gán FF[i][j]=true mặc dù f(i,j) đã được tính.
Wrong answer
- Công thức quy hoạch động sai, xét thiếu trường hợp đặc biệt.
- Gán FF[i][j]=true mà không gán F[i][j]=r.
Tham khảo
Code không đệ quy ở trang con.