Editorial for lcoj: Bài toán xâu ký tự

Hiểu bài toán

Bài toán yêu cầu tìm độ dài của dãy con chung dài nhất (Longest Common Subsequence - LCS) giữa hai xâu ký tự cho trước. Dãy con được hiểu là một xâu thu được bằng cách xóa một số ký tự (có thể không xóa bất kỳ ký tự nào) từ xâu ban đầu sao cho thứ tự các ký tự còn lại được giữ nguyên. Hai xâu a có độ dài m và b có độ dài n được cho. Kết quả cần in ra là một số nguyên duy nhất là độ dài LCS của chúng.

Các cách tiếp cận

Cách Quy hoạch động (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;

int L[3005][3005];

int main()
{
    int m, n;
    cin >> m >> n;
    string str1, str2;
    cin >> str1 >> str2;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (str1[i - 1] == str2[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
    cout << L[m][n];
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Đây là cách tiếp cận chuẩn cho bài toán LCS. Ta sử dụng một mảng 2 chiều dp[i][j] (hoặc L[i][j]) để lưu độ dài LCS của hai xâu con str1[0...i-1] và str2[0...j-1]. Công thức truy hồi:

1. Nếu str1[i-1] == str2[j-1]: Ký tự này có thể là phần tử cuối cùng của LCS. Do đó, dp[i][j] = dp[i-1][j-1] + 1.
2. Nếu str1[i-1] != str2[j-1]: LCS không thể chứa cả hai ký tự này cùng lúc. Ta phải chọn phương án tối ưu giữa việc bỏ ký tự str1[i-1] (tức là lấy dp[i-1][j]) hoặc bỏ ký tự str2[j-1] (tức là lấy dp[i][j-1]). Do đó, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Các giá trị cơ sở là dp[0][j] = 0 và dp[i][0] = 0 (xâu rỗng). Code mẫu sử dụng mảng L với kích thước cố định 3005, đủ để chứa 2500 + một khoảng trống.

Cách Quy hoạch động với tối ưu bộ nhớ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;

    // Chỉ cần mảng 1 chiều để lưu hàng trước đó
    vector<int> prev_row(m + 1, 0);
    vector<int> curr_row(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                curr_row[j] = prev_row[j - 1] + 1;
            } else {
                curr_row[j] = max(prev_row[j], curr_row[j - 1]);
            }
        }
        // Cập nhật hàng trước đó cho vòng lặp tiếp theo
        prev_row = curr_row;
    }
    cout << curr_row[m];
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m)

Cách tiếp cận này tương tự về logic với giải pháp quy hoạch động chuẩn nhưng tối ưu hóa bộ nhớ. Thay vì lưu toàn bộ bảng dp kích thước O(m*n), ta chỉ cần lưu hai hàng liên tiếp: hàng trước đó (prev_row) và hàng hiện tại (curr_row). Sau mỗi lần lặp qua i của xâu s, ta cập nhật prev_row bằng curr_row. Điều này giảm đáng kể bộ nhớ sử dụng, đặc biệt quan trọng khi m và n lớn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có tính chất tối ưu hóa con bài toán con (optimal substructure) và có thể chia nhỏ (overlapping subproblems), phù hợp với Dynamic Programming.
• Giá trị tại dp[i][j] phụ thuộc hoàn toàn vào các giá trị dp của các chỉ số nhỏ hơn.
• Việc tối ưu bộ nhớ từ O(m*n) xuống O(m) là kỹ thuật quan trọng trong các bài toán quy hoạch động 2 chiều.

Lỗi thường gặp

• Sử dụng sai chỉ số mảng (ví dụ dp[i][j] thay vì dp[i-1][j-1]) dẫn đến lỗi logic.
• Không xử lý trường hợp cơ sở (xâu rỗng) hoặc lỗi truy cập ngoài biên mảng.
• Quên cập nhật biến trạng thái khi tối ưu bộ nhớ (không gán prev_row = curr_row ở cuối vòng lặp).
• Độ dài xâu có thể lên tới 2500, cần mảng có kích thước đủ lớn (ví dụ 2600 hoặc 3000).