Hiểu bài toán

Bài toán yêu cầu tìm độ dài xâu con đối xứng (palindrome) dài nhất của một xâu S cho trước. Xâu con được hiểu là xâu thu được bằng cách xóa một số ký tự (có thể không xóa ký tự nào) từ xâu ban đầu, không nhất thiết phải liên tiếp. Ví dụ, với xâu 'bbbab', xâu con đối xứng dài nhất là 'bbbb' với độ dài 4.

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

Cách Quy hoạch động

#include <stdio.h>
#include <string.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    char s[2000];
    scanf("%s", s);
    int n = strlen(s);
    int dp[2000][2000];

    // Base case: xâu con độ dài 1 luôn là đối xứng
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Duyệt theo độ dài xâu con từ 2 đến n
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                if (len == 2) dp[i][j] = 2;
                else dp[i][j] = 2 + dp[i+1][j-1];
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    printf("%d", dp[0][n-1]);
    return 0;
}

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

Đây là cách tiếp cận trực tiếp và phổ biến nhất cho bài toán tìm xâu con đối xứng dài nhất (Longest Palindromic Subsequence). Ta sử dụng bảng 2 chiều dp[i][j] để lưu độ dài xâu con đối xứng dài nhất của xâu S từ chỉ số i đến j.

Công thức truy hồi:

1. Nếu S[i] == S[j]:
   • Nếu i == j: dp[i][j] = 1 (xâu 1 ký tự)
   • Nếu j = i + 1: dp[i][j] = 2 (xâu 2 ký tự giống nhau)
   • Ngược lại: dp[i][j] = dp[i+1][j-1] + 2 (lấy 2 ký tự đầu cuối và cộng với kết quả của phần ở giữa)
2. Nếu S[i] != S[j]:
   • dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (bỏ qua ký tự đầu hoặc cuối)

Ta điền bảng theo thứ tự tăng dần của độ dài xâu con để đảm bảo các giá trị cần thiết đã được tính toán trước.

Cách Quy hoạch động tối ưu

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    char s[2001];
    fgets(s, 2001, stdin);
    s[strcspn(s, "\n")] = '\0';
    int n = strlen(s);

    if (n == 0) {
        printf("0\n");
        return 0;
    }

    // Phân bổ động bộ
    int **dp = (int **)calloc(n, sizeof(int *));
    for (int i = 0; i < n; i++) {
        dp[i] = (int *)calloc(n, sizeof(int));
    }

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

    // Duyệt từ dưới lên trên
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = 2 + dp[i+1][j-1];
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }

    printf("%d", dp[0][n-1]);

    // Giải phóng bộ nhớ
    for (int i = 0; i < n; i++) free(dp[i]);
    free(dp);
    return 0;
}

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

Đây là cách triển khai khác của cùng thuật toán quy hoạch động. Thay vì duyệt theo độ dài, cách này duyệt từ dưới lên trên (từ cuối xâu về đầu).

Ta khởi tạo dp[i][i] = 1 cho mọi i. Sau đó, với mỗi i từ n-1 về 0, ta duyệt j từ i+1 đến n-1. Khi này, dp[i+1][j-1], dp[i+1][j], dp[i][j-1] đều đã được tính toán trước đó do thứ tự duyệt.

Cách này cũng cho cùng độ phức tạp O(n^2) về thời gian và bộ nhớ, nhưng có thể dễ hiểu hơn với một số người.

Cách Quy hoạch động với chu kỳ

#include <stdio.h>
#include <string.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    char s[2000];
    scanf("%s", s);
    int n = strlen(s);
    int dp[2000][2000];

    // Khởi tạo
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) dp[i][j] = 1;
            else dp[i][j] = 0;
        }
    }

    // Duyệt theo độ dài k từ 2 đến n
    for (int k = 2; k <= n; k++) {
        for (int i = 0; i <= n - k; i++) {
            int j = i + k - 1;
            // Mặc định lấy max của 2 trường hợp bỏ đầu hoặc bỏ cuối
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

            // Nếu 2 ký tự đầu cuối giống nhau
            if (s[i] == s[j]) {
                if (k == 2) dp[i][j] = 2;
                else dp[i][j] = dp[i + 1][j - 1] + 2;
            }
        }
    }

    printf("%d", dp[0][n - 1]);
    return 0;
}

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

Đây là cách tiếp cận khác cùng thuật toán quy hoạch động, nhưng được trình bày theo cách nhấn mạnh vào việc điền bảng theo chu kỳ.

Cấu trúc lặp:

1. Vòng lặp ngoài cùng duyệt k từ 2 đến n (độ dài xâu con)
2. Vòng lặp trong duyệt i từ 0 đến n-k để chọn xâu con độ dài k

Ưu điểm của cách này là rõ ràng về mặt logic: ta tính toán cho các xâu con ngắn trước, sau đó mới dùng kết quả đó cho các xâu con dài hơn.

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

Bài học kinh nghiệm

• Bài toán có thể giảm về bài toán tìm xâu con chung dài nhất (LCS) giữa xâu S và xâu đảo ngược của S, nhưng cách quy hoạch động trực tiếp hiệu quả hơn về mặt triển khai và tối ưu bộ nhớ.
• Quy hoạch động là cách tiếp cận tối ưu với độ phức tạp O(n^2), phù hợp với ràng buộc n ≤ 2000.
• Có thể tối ưu bộ nhớ từ O(n^2) xuống O(n) bằng cách chỉ lưu 2 hàng liên tiếp của bảng DP nếu chỉ cần độ dài (không cần in ra xâu).

Lỗi thường gặp

• Độ dài xâu con có thể là 1 hoặc 2, cần xử lý các trường hợp cơ sở này riêng trong công thức truy hồi.
• Thứ tự duyệt trong quy hoạch động phải đảm bảo khi tính dp[i][j] thì các giá trị cần dùng (dp[i+1][j-1], dp[i+1][j], dp[i][j-1]) đã được tính trước đó.
• Lỗi truy cập ngoài biên mảng khi j = i+1, dp[i+1][j-1] sẽ là dp[i+1][i] (vô nghĩa). Cần xử lý riêng cho trường hợp này.
• Cần phân biệt rõ giữa 'xâu con liên tiếp' (substring) và 'xâu con không liên tiếp' (subsequence). Bài toán này yêu cầu xâu con không liên tiếp.