最长回文子序列

定义

最长回文子序列（Longest Palindromic Subsequence，LPS）是一个字符串的所有回文子序列中长度最大的一个。它与最长回文子串不同：子序列可以删除中间字符，子串必须连续。

求解算法

思路

设 \(a[1\ldots n]\) 为原字符串，\(f[i][j]\) 为子串 \(a[i\ldots j]\) 的最长回文子序列长度。

\[ f[i][j] = \begin{cases} f[i+1][j-1] + 2, & a[i] = a[j], \\ f[i+1][j], & a[i] \ne a[j] \text{ 且 } f[i+1][j] > f[i][j-1], \\ f[i][j-1], & a[i] \ne a[j] \text{ 且 } f[i+1][j] \le f[i][j-1]. \end{cases} \]

边界条件为 \(f[i][i] = 1\)；当 \(i > j\) 时取 \(0\)。按区间长度从小到大枚举即可，答案为 \(f[1][n]\)。

实现

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 2005;
int n, dp[MAXN][MAXN];
char s[MAXN];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);

    for (int i = 1; i <= n; ++i) dp[i][i] = 1;
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }

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