Dãy Con Palindrome Dài Nhất (Longest Palindromic Subsequence)

Giới thiệu

Dãy con palindrome dài nhất là dãy con của một dãy cho trước, mà dãy con đó đọc xuôi và đọc ngược đều giống nhau. Bài toán yêu cầu tìm độ dài của dãy con palindrome dài nhất.

Đầu vào và Đầu ra

Đầu vào: Một chuỗi ký tự, ví dụ "ABCDEEAB".
Đầu ra: Độ dài dãy con palindrome dài nhất. Ở đây là 4 (dãy con "AEEA").

Thuật toán Quy hoạch động

Sử dụng bảng lenTable[n][n] lưu độ dài dãy con palindrome dài nhất từ chỉ số i đến j.

palSubSeqLen(str)
Begin
    n = độ dài chuỗi
    tạo bảng lenTable n x n, điền 1 vào đường chéo chính
    for col := 2 to n do
        for i := 0 to n - col do
            j := i + col - 1
            if str[i] = str[j] and col = 2 then
                lenTable[i, j] := 2
            else if str[i] = str[j] then
                lenTable[i, j] := lenTable[i+1, j-1] + 2
            else
                lenTable[i, j] := max(lenTable[i, j-1], lenTable[i+1, j])
            done
        done
    return lenTable[0, n-1]
End

Ví dụ C++

#include <iostream>
using namespace std;

int max(int x, int y) { return (x > y) ? x : y; }

int palSubseqLen(string str) {
    int n = str.size();
    int lenTable[n][n];
    for (int i = 0; i < n; i++)
        lenTable[i][i] = 1;

    for (int col = 2; col <= n; col++) {
        for (int i = 0; i < n - col + 1; i++) {
            int j = i + col - 1;
            if (str[i] == str[j] && col == 2)
                lenTable[i][j] = 2;
            else if (str[i] == str[j])
                lenTable[i][j] = lenTable[i+1][j-1] + 2;
            else
                lenTable[i][j] = max(lenTable[i][j-1], lenTable[i+1][j]);
        }
    }
    return lenTable[0][n-1];
}

int main() {
    string sequence = "ABCDEEAB";
    cout << "Độ dài dãy con palindrome dài nhất: " << palSubseqLen(sequence);
    return 0;
}

Kết quả

Độ dài dãy con palindrome dài nhất: 4