Dãy con đối xứng dài nhất (Longest Palindromic Subsequence) trong C++

Cho chuỗi s, tìm độ dài dãy con đối xứng dài nhất.

Ví dụ: "bbbab" → 4 ("bbbb").

Thuật toán (DP LCS với chuỗi đảo)

1. Đảo chuỗi s thành x.
2. Bài toán thành Longest Common Subsequence của s và x.
3. DP 2D: dp[i][j] = max(dp[i-1][j], dp[i][j-1]); nếu s[i]==x[j] thì dp[i][j] = max(dp[i][j], 1+dp[i-1][j-1]).

Mã nguồn C++

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

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        string x = s;
        reverse(x.begin(), x.end());
        int n = s.size();
        if (!n) return 0;
        s = " " + s; x = " " + x; // 1-indexed
        vector> dp(n+1, vector(n+1,0));
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if (x[i] == s[j]) dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1]);
            }
        return dp[n][n];
    }
};

int main() {
    Solution ob;
    cout << ob.longestPalindromeSubseq("bbbab"); // 4
    return 0;
}

Đầu vào / Đầu ra

Input: "bbbab"

Output: 4