Hiểu bài toán

Bài toán yêu cầu tìm độ dài của dãy con đối xứng dài nhất trong một dãy số nguyên cho trước. Dãy con đối xứng là một dãy con (các phần tử liên tiếp hoặc không liên tiếp? Dựa trên các solution, dãy con ở đây là dãy liên tiếp) mà khi đọc từ trái sang phải và từ phải sang trái đều như nhau. Ví dụ: [1, 2, 3, 2, 1] là một dãy con đối xứng. Với ràng buộc n ≤ 1000, chúng ta có thể sử dụng thuật toán quy hoạch động với độ phức tạp O(n^2).

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

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

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

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int maxlen = 1;
    vector<vector<bool>> dp(n, vector<bool>(n, false));

    // len = 1
    for (int i = 0; i < n; i++) dp[i][i] = true;

    // len = 2
    for (int i = 0; i < n - 1; i++) {
        if (a[i] == a[i + 1]) {
            dp[i][i + 1] = true;
            maxlen = 2;
        }
    }

    // len >= 3
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (a[i] == a[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                maxlen = max(maxlen, len);
            }
        }
    }

    cout << maxlen << "\n";
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Ta sử dụng mảng 2 chiều dp[i][j] để đánh dấu dãy con từ chỉ số i đến j có phải là dãy đối xứng hay không.

1. Khởi tạo: Các dãy con độ dài 1 luôn đối xứng (dp[i][i] = true). Các dãy con độ dài 2 đối xứng nếu a[i] == a[i+1].
2. Công thức truy hồi: Với độ dài len từ 3 đến n, dãy con từ i đến j đối xứng khi và chỉ khi a[i] == a[j] và dãy con bên trong từ i+1 đến j-1 đã được xác định là đối xứng (dp[i+1][j-1] == true).
3. Trong quá trình cập nhật, ta luôn giữ lại độ dài lớn nhất tìm được.

Cách Quy hoạch động (Tối ưu không gian)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<vector<bool>> dp(n + 1, vector<bool>(n + 1, false));
    int ans = 1;

    for (int i = 1; i <= n; i++) {
        dp[i][i] = true;
    }

    for (int i = 1; i < n; i++) {
        if (a[i] == a[i + 1]) {
            dp[i][i + 1] = true;
            ans = 2;
        }
    }

    for (int len = 3; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            if (a[i] == a[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                ans = len;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Đây là biến thể sử dụng chỉ số 1-based để dễ dàng hình dung hơn. Logic hoàn toàn tương tự với Approach 1. Bài toán này với n=1000 thì O(n^2) là chấp nhận được (khoảng 1 triệu phép tính), nên việc tối ưu không gian xuống O(n) không phải là bắt buộc nhưng là một kỹ thuật tốt để biết.

Cách Mở rộng từ tâm (Trung tâm)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> s(n);
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }
    int max_len = 1;
    // Duyệt qua từng vị trí làm tâm
    for(int center = 0; center < n; center++)
    {
        // Trường hợp tâm là một phần tử (độ dài lẻ)
        int l = center - 1, r = center + 1;
        while(l >= 0 && r < n && s[l] == s[r]) {
            if (r - l + 1 > max_len) max_len = r - l + 1;
            l--; r++;
        }

        // Trường hợp tâm là hai phần tử (độ dài chẵn)
        if (center + 1 < n && s[center] == s[center+1]) {
            if (2 > max_len) max_len = 2;
            l = center - 1; r = center + 2;
            while(l >= 0 && r < n && s[l] == s[r]) {
                if (r - l + 1 > max_len) max_len = r - l + 1;
                l--; r++;
            }
        }
    }
    cout << max_len;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Phương pháp này không sử dụng bảng quy hoạch động mà thay vào đó coi mỗi phần tử (hoặc cặp phần tử) làm tâm và mở rộng ra hai phía.

1. Duyệt qua mỗi chỉ số center từ 0 đến n-1.
2. Với mỗi center, kiểm tra dãy con đối xứng lẻ (tâm là center) bằng cách mở rộng chỉ số l sang trái và r sang phải.
3. Kiểm tra dãy con đối xứng chẵn (tâm nằm giữa center và center+1) nếu a[center] == a[center+1].
4. Cập nhật độ dài lớn nhất. Phương pháp này tốn ít bộ nhớ hơn (O(1)), nhưng trong trường hợp xấu nhất vẫn có độ phức tạp thời gian O(n^2).

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 con (optimal substructure) và lặp lại (overlapping subproblems) nên phù hợp với quy hoạch động.
• Cần phân biệt rõ giữa dãy con đối xứng liên tiếp và không liên tiếp. Các giải pháp trên đều giả định liên tiếp (palindromic substring).
• Cần chú ý xử lý các trường hợp cơ sở: dãy con độ dài 1 và 2 trước khi tính toán các độ dài lớn hơn.

Lỗi thường gặp

• Lỗi chỉ số mảng: Khi truy cập dp[i+1][j-1], cần đảm bảo i+1 <= j-1 (tức là độ dài >= 3). Các giải pháp đúng đã kiểm soát điều này bằng vòng lặp len.
• Quên cập nhật độ dài lớn nhất cho các trường hợp cơ sở (độ dài 1 và 2).
• Sử dụng sai kiểu dữ liệu hoặc không khởi tạo giá trị mặc định cho bảng DP.