cpp最长回文子序列

在C++中，计算字符串中最长的回文子序列（Longest Palindromic Subsequence, LPS）是一个常见的动态规划问题。回文是指正读反读都一样的字符序列，比如"abcba"就是一个回文。

经典的KMP算法或者Manacher's Algorithm通常用于解决这个问题，因为它们的时间复杂度较低，例如Manacher's算法可以达到O(n)的时间复杂度。动态规划方法的一个典型思路是使用二维数组dp[i][j]，其中dp[i][j]表示字符串s从位置i到j之间的最长回文子序列长度。初始时，所有单个字符都是其自身的LPS，然后通过比较s[i-1]和s[j+1]，以及当前子串的左右边界是否相等，逐步更新dp数组。

下面是一个简单的动态规划解决方案：

int longestPalindromeSubseq(string s) {
    int n = s.length();
    vector<int> dp(n, 0);
    
    for (int i = 1; i < n; ++i) {
        if (s[i] == s[i - 1]) {
            dp[i] = dp[i - 1] + 2;
        } else {
            dp[i] = max(dp[i - 1], // 如果首尾字符不相同，取左边的最长
                        dp[i - 2]); // 否则取左右两边中的较长者
        }
    }

    return dp[n - 1]; // 返回整个字符串的最大回文子序列长度
}