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 S1 và S2 cho trước. Xâu con chung là một xâu được tạo ra bằng cách bỏ đi một số (có thể không có) ký tự từ xâu gốc mà không làm thay đổi thứ tự các ký tự còn lại. Ví dụ, với "ABC" và "ACB", xâu con chung chung dài nhất là "AB" hoặc "AC" có độ dài 2. Chúng ta cần output độ dài này.

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

Cách Quy hoạch động cơ bản (Bảng 2D)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("sub.inp", "r", stdin);
    freopen("sub.out", "w", stdout);
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);

    int n = s1.size();
    int m = s2.size();

    // dp[i][j] lưu độ dài LCS của s1[0...i-1] và s2[0...j-1]
    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 (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

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

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

Đây là cách tiếp cận chuẩn của quy hoạch động. Ta tạo một bảng 2 chiều dp với dp[i][j] là độ dài LCS của hai xâu con s1[0...i-1] và s2[0...j-1]. Công thức truy hồi:

1. Nếu s1[i-1] == s2[j-1]: Ký tự cuối cùng của hai xâu con này giống nhau, ta có thể nối nó vào LCS của hai xâu con trước đó. Vậy dp[i][j] = dp[i-1][j-1] + 1.
2. Nếu khác nhau: LCS không thể chứa cả hai ký tự cuối này. Ta phải loại bỏ một trong hai và lấy max của các kết quả trước đó: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Code trên implement đúng logic này với độ phức tạp O(n*m) cả thời gian và bộ nhớ.

Cách Quy hoạch động tối ưu bộ nhớ (Bảng 1D)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    freopen("sub.inp" , "r" , stdin);
    freopen("sub.out" , "w" , stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s1 , s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    vector<int>a(m+1 , 0) , b(m+1 , 0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s1[i-1] == s2[j-1]) a[j] = b[j-1]+1;
            else a[j] = max(b[j] , a[j-1]);
        }
        b = a;
    }
    cout << a[m];
    return 0;
}

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

Khi tính dp[i][j], ta chỉ cần truy cập hàng i-1 (dãy dp[i-1][...]) và các cột đã được tính trước đó của hàng i (cột j-1). Do đó, ta không cần lưu toàn bộ bảng n x m. Ta chỉ cần 2 hàng: b (tương ứng hàng i-1) và a (tương ứng hàng i đang tính).

• Vòng lặp i duyệt qua các ký tự của s1.
• b lưu kết quả của lần lặp trước (trước khi cập nhật a).
• a[j] được tính dựa trên b (hàng trên) và a[j-1] (trái).
• Cuối vòng lặp i, ta gán b = a để chuẩn bị cho bước tiếp theo. Cách này giảm bộ nhớ từ O(n*m) xuống O(m).

Cách Tối ưu bộ nhớ tối đa (Duyệt 2 dòng)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() 
{
    freopen("sub.inp","r",stdin);
    freopen("sub.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int n = s1.size();
    int m = s2.size();
    vector<vector<int>> dp(2, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) 
    {
        int ii = i % 2;
        int jj = (i - 1) % 2;
        for (int j = 1; j <= m; j++) 
        {
            if (s1[i - 1] == s2[j - 1]) dp[ii][j] = dp[jj][j - 1] + 1;
            else dp[ii][j] = max(dp[jj][j], dp[ii][j - 1]);
        }
    }
    cout << dp[n % 2][m];
    return 0;
}

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

Đây là biến thể khác của tối ưu bộ nhớ. Thay vì dùng hai vector riêng biệt a và b rồi copy, ta dùng mảng 2 chiều có 2 hàng dp[2][m+1].

• Chỉ số hàng được tính bằng i % 2. Khi đang tính hàng i, ta cần dữ liệu từ hàng i-1, tức là chỉ số (i-1) % 2.
• dp[i%2][j] là kết quả hiện tại.
• dp[(i-1)%2][j] là kết quả của hàng trên. Cách này cũng có không gian O(m) và thường hiệu năng tốt hơn do tránh thao tác copy vector.

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

Bài học kinh nghiệm

• Bài toán LCS là bài kinh điển của Quy hoạch động, chia nhỏ vấn đề từ xâu con ngắn hơn.
• Trạng thái dp[i][j] phụ thuộc vào dp[i-1][j-1], dp[i-1][j], dp[i][j-1].
• Có thể tối ưu bộ nhớ đáng kể từ O(n*m) xuống O(min(n, m)) bằng cách chỉ cần lưu hàng trước đó.

Lỗi thường gặp

• Lỗi index: Do quy hoạch động thường bắt đầu từ 1 để xử lý điều kiện biên, cần chú ý chuyển đổi index từ xâu (bắt đầu từ 0) sang dp table (bắt đầu từ 1). Ví dụ: s1[i-1] khi dp[i].
• Quên xử lý xâu rỗng: Đảm bảo bảng dp khởi tạo giá trị 0 cho hàng 0 và cột 0.
• Sử dụng cin >> s1 >> s2: Nếu xâu input chứa khoảng trắng, cin sẽ chỉ đọc đến khoảng trắng đầu tiên. Solution 3 dùng cin có thể fail với test có khoảng trắng, trong khi Solution 1 và 2 dùng getline an toàn hơn cho mọi loại xâu.