NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 25 题

#include <iostream>
using namespace std;
int lps(string seq, int i, int j)
{
    int len1, len2;
    if (i == j)
        return 1;
    if (i > j)
        return 0;
    if (seq[i] == seq[j])
        return lps(seq, i + 1, j - 1) + 2;
    len1 = lps(seq, i, j - 1);
    len2 = lps(seq, i + 1, j);
    if (len1 > len2)
        return len1;
    return len2;
}
int main()
{
    string seq = "acmerandacm";
    int n = seq.size();
    cout << lps(seq, 0, n - 1) << endl;
    return 0;
}

输出：_________

看到 lps 递归定义 → 先想最长回文子序列（可删字符），不是子串

易混：lps 是子序列（可删），不是子串（必须连续）

考点：最长回文子序列（LPS）

程序在做什么

输入字符串，递归求最长回文子序列长度：两端字符相等时 +2 向内递归，否则取删左或删右的较大值。