Bài viết đã được chuyển đến Thư viện VNOI mới.

I. Vấn đề cơ bản:

Đề bài: Cho 2 dãy số nguyên a gồm m phần tử, b gồm n phần tử. Tìm độ dài dãy con chung dài nhất (LCS - Longest common subsequence) của hai dãy a và b.

Bài toán này là một trong những bài toán cơ bản nhất trong Quy hoạch động có thể tìm thấy trong bất cứ quyển sách nào nói về Quy hoạch động. Ta có thể dễ dàng chứng minh và tìm ra công thức Quy hoạch động một cách nhanh chóng.

Ta có thể gọi F[i][j] = độ dài dãy con chung dài nhất xét khi xét i phần tử đầu tiên của dãy a và j phần tử đầu tiên của dãy b.

Dễ dàng nhận thấy:

\( F\left[i,j\right] = max \begin{cases} \textrm{ } F\left[i - 1,j - 1\right] + 1 & \mbox{ nếu } a[i] = b[j] \\ \mbox{max}\left(F\left[i - 1, j\right],F\left[i, j - 1\right]\right) & \mbox{ nếu } a[i] \ne b[j] \\ \end{cases} \)

II.   Vấn đề mở rộng:

1.     Kỹ thuật đảo nhãn trong Quy hoạch động:

Đề bài: Cho hai xâu A và B (|A| ≤ 10⁶, |B| ≤ 5000), tìm xâu con chung dải nhất (Longest Common Subquence) của hai xâu trên.

Cách giải cơ bản được nêu ở phần I. có thể giải quyết bài toán này trong O(|A|.|B|) nhưng phương pháp này là không khả thi trong bài này bởi vì |A|.|B| ≤ 5*10⁹.

Có thể nhận thấy rằng, độ dài xâu con chung dài nhất của hai xâu A và B ≤ min(|A|, |B|). Cách giải thông thường là gọi F[i][j] = k, với ý nghĩa F[i][j] là độ dài xâu con chung dài nhất khi xét i ký tự đầu tiên trong A và j ký tự đầu tiên trong B. F[i][[j] = k nghĩa là k là độ dài dài nhất khi xét i ký tự đầu tiên trong A và j ký tự đầu tiên trong B. Sử dụng tư tưởng gần như trên, ta gọi F[i][k] = j tức là xâu con chung dài nhất của i ký tự đầu tiên trong A có độ dài k thì j là vị trí nhỏ nhất trong B để A và B có xâu con chung độ dài là k.

Phương pháp làm như trên được gọi là đảo nhãn trong Quy hoạch động,

Cách tính F[i][k] này khá đơn giản. Trước tiên ta gọi next [i][ch] vị trí đầu tiên xuất hiện ký tự ch trong trong đoạn [i, |A|] của xâu A.

\( next\left[i,ch\right] = \begin{cases} \textrm{ } next\left[i + 1,ch\right] & \mbox{ nếu } A[j] \neq ch \\ i & \mbox{ nếu } A[i] = ch \\ |A| + 1 & \mbox{ nếu } i = |A| + 1 \\ \end{cases} \)

Việc còn lại là tính hàm F, việc này khá đơn giản.

\( F\left[i,k\right] = min \begin{cases} \textrm{ }F\left[i - 1, k\right]\\ next[F[i - 1][k - 1] + 1, B[i]] & \mbox{ nếu } F[i - 1][k - 1] \neq |A| + 1 \\ \end{cases} \)

Nếu F[i, k] < n + 1 thì tồn tại một xâu con chung có độ dài là k.

Độ phức tạp tính toán là O(|B|²).

Có thể tham khảo đoạn code sau:

scanf(“%s”, a);
scanf(“%s”, b);
m = strlen(a); n = strlen(b);

for (int i = 0; i < 256; i++)
     next[n + 2][i] = next[n + 1][i] = n + 1;

for (int i = n; i > 0; i--)
     for (int j = 0; j < 256; j++)
     next[i][j] = (a[i - 1] == j ? i : next[i + 1][j]);

for (int i = 0; i < 256; i++) next[0][i] = next[1][i];
for (int i = 1; i <= m; i++) f[0][i] = n + 1;

for (int i = 1; i <= m; i++)
     for (int j = 1; j <= m; j++) f[i][j] = n + 1;

for (int j = 1; j <= m; j++)
     for (int i = j; i <= m; i++)
     f[i][j] = min(f[i - 1][j], next[f[i - 1][j - 1] + 1][b[i - 1]]);

ans = 0;
for (int i = 1; i <= m; i++)
     for (int j = 1; j <= m; j++)
     if (f[i][j] < n + 1) ans = max(ans, j);
printf(“%d”, ans);

Áp dụng: LCS2X (VOI2014).

2.     Cách tiếp cận đánh giá để làm giảm độ phức táp bài toán:

Đề bài: Cho 2 dãy số nguyên a gồm m phần tử, b gồm n phần tử. Tìm độ dài dãy con chung dài nhất của hai dãy a và b thoả mãn độ chênh lệch giữa hai phần tử trước sau trong dãy con chung không vượt quá K.

Để giải quyết vấn đề trên ta xét một hàm quy hoạch động với mô hình như sau.

Trước tiên ta hiểu vấn đề như sau: Vẫn gọi LCS[i][j] là độ dài dãy con chung dài nhất từ 1 đến i ở dãy thứ nhất và 1 đến j ở dãy thứ hai. Và LCS[i][j]>0 nếu a[i]=b[j] ngược lại bằng 0.

Vậy LCS[i][j]=max(LCS[x][y])+1 với a[i]=b[j] và |a[i] – a[x]| ≤ K(1≤x<i, 1≤y<j)

Bây giờ ta nhận thấy vấn đề như sau:

Giả sử LCS[i][j]=LCS[x][y]+1 (Ta giả sử đã tìm được x, y thoả điều kiện). Ta xét các trường hợp sau:

     + LCS[x][y]=0 thì i trong dãy a (hay j trong dãy b) là phần tử bắt đầu của dãy con chung.

     + LCS[x][y]>0 thì chắc chắn a[x]=b[y] và |a[i]-a[x]|=|a[i]-b[y]|≤K

Ta nhận thấy LCS[1..i][j] ta chỉ cần giữ lại phần tử nào mang giá trị lớn nhất. Không cần phải lưu hết tất cả LCS[1..i][j] mà chỉ cần lưu một giá trị LCS[j] duy nhất là giá trị lớn nhất trong tất cả các LCS[1..i][j]. (Nếu lưu hết ta chỉ làm mất thời gian tìm kiếm max(LCS[x][y]), mà điều kiện ràng buộc như đã xét ở 2 trường hợp cũng chỉ phục thuộc vào b[j] mà thôi).

Việc còn lại chỉ là tìm max(LCS[y]) mà thôi. Việc tìm max(LCS[y]) này khá dễ dàng, với mỗi lần xét tới i trong dãy a, ta lại bắt đầu cập nhật max(LCS[y])=0, sau đó tiến hành duyệt j trong dãy b, ở mỗi bước duyệt j ta cập nhất max(LCS[y]) với điều kiện max(LCS[y])=max(max(LCS[y]), LCS[j]) nếu |a[i]-b[j]|≤K. Đồng thời ta cũng cần cập nhật LCS[j] nếu a[i]=b[j] thông qua max(LCS[y]) trước đó. Kết quả là max(LCS[j]) (1≤j≤n).

Như thế ta đã có một giải thuật với độ phức tạp O(m*n) giải quyết vấn đề. Ta vẫn có thể áp dụng cách này vào giải bài toán LCS.

Ta có thể tham khảo đoạn code sau:

scanf( “%d  %d  %d”, &m, &n, &K) ;
for (int i = 0; i < m; i++) scanf(“%d”, &a[i]);
for (int i = 0; i < n; i++) scanf(“%d”, &b[i]);

int ans = 0;
for (int i = 0; i < m; i++)
{
     int mmax = 0;
     for (int j = 0; j < n; j++)
     {
           int premax = mmax;
           if (abs(a[i] – b[j]) <= K) mmax = max(LCS[j], mmax);
           if (a[i] = b[j]) LCS[j] = max(LCS[j], premax + 1);
           ans = max(ans, LCS[j]);
     {
}
printf(“%d”, ans);

Áp dụng: LCS2X (VOI2014), VOSLIS.