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;
}
```
输出：_________

请写出程序的输出结果。

答案

5

题解

考点定位

本题考「最长回文子序列递归」,对应大纲 4.3.2 DP（难度【4】）。

解题过程

lps(seq,i,j)：i==j 返 1、i>j 返 0、端点相等 +2、否则两侧取大。串 acmerandacm（长 11）：最长回文子序列长 = 5。

答案：5。

易错提醒

① 递归无记忆化但数据小可算；② 找一个长 5 回文（如 amaa?a…手动核）：c…m…a…a…c 类；区间 DP 表也可。