Quy Hoạch Động Chuỗi: LCS & Edit Distance

1. Không gian trạng thái hai tiền tố (2-prefix state)

Trong xử lý chuỗi ký tự thi đấu, các bài toán so khớp, tìm chuỗi tương đồng hay biến đổi xâu thường thao tác trên hai chuỗi $A$ (độ dài $N$) và $B$ (độ dài $M$).

• Nguyên lý Thiết kế Trạng thái: Ta định nghĩa trạng thái dựa trên Cặp tiền tố của hai chuỗi:

$dp[i][j]$ đại diện cho kết quả tối ưu khi xét tiền tố $A[1 \dots i]$ (gồm $i$ ký tự đầu của $A$) và tiền tố $B[1 \dots j]$ (gồm $j$ ký tự đầu của $B$).

• Trường hợp cơ sở (Base Cases): Khi một trong hai tiền tố có độ dài bằng 0 ($i = 0$ hoặc $j = 0$), tương đương với chuỗi rỗng $\varepsilon$.

2. Dãy con chung dài nhất (longest common subsequence — LCS)

2.1. Bản chất toán học & hệ thức truy hồi

• Định nghĩa: Dãy con là dãy thu được bằng cách xóa đi một số ký tự mà không làm thay đổi thứ tự của các ký tự còn lại.
• State Definition: $dp[i][j]$ là độ dài của dãy con chung dài nhất giữa $A[1 \dots i]$ và $B[1 \dots j]$.
• Base Cases: dp[0][j] = 0 và dp[i][0] = 0 với mọi $i, j$.
• State Transition: So sánh ký tự đuôi $A[i]$ và $B[j]$: 1. Nếu $A[i] == B[j]$: Ký tự này chắc chắn thuộc LCS chung: $$dp[i][j] = 1 + dp[i-1][j-1]$$

1. Nếu A[i] != B[j]: Bỏ qua $A[i]$ hoặc bỏ qua $B[j]$ để lấy phương án tốt hơn: $$dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$$

• Độ phức tạp: Thời gian $\mathcal{O}(N \cdot M)$, Bộ nhớ $\mathcal{O}(N \cdot M)$.

2.2. Kỹ thuật khôi phục xâu LCS tối ưu (traceback)

Từ ô kết quả $(N, M)$ trên bảng phương án 2D:

1. Nếu $A[i] == B[j] \implies$ Thêm $A[i]$ vào xâu kết quả, lùi chéo về $(i-1, j-1)$.
2. Nếu $A[i] \ne B[j] \implies$ Đi về ô có giá trị lớn hơn: lên trên $(i-1, j)$ nếu $dp[i-1][j] \ge dp[i][j-1]$, ngược lại sang trái $(i, j-1)$.
3. Dừng lại khi $i = 0$ hoặc $j = 0$. Đảo ngược xâu kết quả thu được.

3. Khoảng cách biến đổi xâu (Edit Distance / Levenshtein Distance)

3.1. Bản chất 3 phép biến đổi

Cần tìm số phép biến đổi ít nhất để biến xâu $A$ thành xâu $B$. Các phép thao tác hợp lệ gồm:

1. Chèn (Insert): Thêm 1 ký tự vào xâu $A$.
2. Xóa (Delete): Xóa 1 ký tự khỏi xâu $A$.
3. Thay thế (Replace): Đổi 1 ký tự của $A$ thành ký tự khác.

3.2. Hệ thức chuyển trạng thái

• State Definition: $dp[i][j]$ là số thao tác ít nhất biến $A[1 \dots i]$ thành $B[1 \dots j]$.
• Base Cases:
• dp[i][0] = i (Biến xâu độ dài $i$ thành xâu rỗng cần $i$ phép xóa).
• dp[0][j] = j (Biến xâu rỗng thành xâu độ dài $j$ cần $j$ phép chèn).
• State Transition:
• Nếu $A[i] == B[j] \implies dp[i][j] = dp[i-1][j-1]$ (Không tốn chi phí).
• Nếu A[i] != B[j]: $$dp[i][j] = 1 + \min(\underbrace{dp[i-1][j-1]}_{\text{Thay thế}}, \underbrace{dp[i-1][j]}_{\text{Xóa}}, \underbrace{dp[i][j-1]}_{\text{Chèn}})$$

4. Phân biệt rạch ròi: Xâu con đối xứng (substring) vs dãy con đối xứng (subsequence)

Đây là tử huyệt thuật ngữ cực kỳ quan trọng trong lập trình thi đấu:

4.1. Xâu con liên tiếp đối xứng dài nhất (longest palindromic substring)

• Đặc tính: Các ký tự phải liên tiếp liền kề nhau.
• State Definition: $dp[i][j]$ kiểu boolean, nhận giá trị true nếu đoạn con liên tiếp $S[i \dots j]$ là một xâu đối xứng.
• Transition: $dp[i][j] = (S[i] == S[j]) \land dp[i+1][j-1]$.
• Duyệt: Theo độ dài xâu con $len = 1 \to N$.

4.2. Dãy con không liên tiếp đối xứng dài nhất (longest palindromic subsequence)

• Đặc tính: Các ký tự không cần liên tiếp.
• State Definition: $dp[i][j]$ là độ dài lớn nhất của dãy con đối xứng trích xuất từ đoạn $S[i \dots j]$.
• Transition:
• Nếu $S[i] == S[j] \implies dp[i][j] = 2 + dp[i+1][j-1]$.
• Nếu $S[i] \ne S[j] \implies dp[i][j] = \max(dp[i+1][j], dp[i][j-1])$.
• Cách giải tương đương: Tính $LCS$ giữa xâu $S$ và xâu đảo ngược $S^R$!

5. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy lệch chỉ số 0-based của Xâu ký tự với 1-based của Bảng DP: * Trong C++, string có chỉ số từ 0 đến $N-1$. Khi truy cập ký tự thứ $i$ trong bảng DP 1-based, phải viết A[i - 1] thay vì A[i].
2. Bẫy thứ tự duyệt trong Quy hoạch động trên Đoạn con Palindrome: * Trạng thái $dp[i][j]$ phụ thuộc vào $dp[i+1][j-1]$ (đoạn ngắn hơn). Nếu duyệt $i$ từ $1 \to N$ xuôi thì ô $dp[i+1][\dots]$ chưa được tính $\implies$ Kết quả sai! * Quy tắc đúng: Luôn duyệt theo độ dài $len = 1 \to N$, sau đó duyệt điểm đầu $i = 1 \to N - len + 1$ và $j = i + len - 1$.
3. Bẫy khởi tạo Base Case của Edit Distance: * Quên khởi tạo cột $0$ (dp[i][0] = i) và hàng $0$ (dp[0][j] = j) sẽ dẫn đến toàn bộ bảng nhận giá trị rác.

6. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Dãy con chung dài nhất (LCS) kèm khôi phục xâu

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    if (!(cin >> a >> b)) return 0;

    int n = a.size();
    int m = b.size();
    if (n == 0 || m == 0) {
        cout << 0 << "\n\n";
        return 0;
    }

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m] << "\n";

    // Khôi phục xâu LCS
    string lcs_str = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {

        if (a[i - 1] == b[j - 1]) {
            lcs_str.push_back(a[i - 1]);
            --i;
            --j;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }
    reverse(lcs_str.begin(), lcs_str.end());
    cout << lcs_str << "\n";

    return 0;
}

Mẫu 2: Khoảng cách biến đổi xâu (Edit Distance)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    if (!(cin >> a >> b)) return 0;

    int n = a.size();
    int m = b.size();

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    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 (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + min({dp[i - 1][j - 1], // Replace
                                    dp[i - 1][j],     // Delete
                                    dp[i][j - 1]});   // Insert
            }
        }
    }

    cout << dp[n][m] << "\n";
    return 0;
}