Longest Palindromic Subsequence หาลำดับย่อยพาลินโดรมที่ยาวที่สุดใน C++

ให้สตริง s หาความยาวของ longest palindromic subsequence (LPS) สมมติความยาวสูงสุด 1000

ตัวอย่าง: "bbbab" → 4 (subsequence "bbbb")

วิธีแก้ปัญหา (DP: LCS กับสตริงกลับ)

LPS(s) = LCS(s, reverse(s))

1. x = reverse(s), n = s.length()
2. สร้าง DP table (n+1)×(n+1)
3. dp[i][j] = max(dp[i][j-1], dp[i-1][j])
4. ถ้า x[i] == s[j]: dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1])
5. คืน dp[n][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;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                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");
    return 0;
}

Input

"bbbab"

Output

4