3025 - 最长回文子序列

给定字符串s,从其中取出部分字符,并保持前后顺序不变,组成的字符串成为原字符串的子序列。例如在abcdbca中,abc、acc、acdca等均为子序列。如果子串满足回文规律,则称回文子序列。 求其最长回文子序列的长度。

输入

一个字符串,长度不大于1000.

输出

最长回文子序列长度。

样例

输入

abcdbca

输出

5

提示

样例中,abcdbca的最长回文子序列为abdba、acdca、acbca,长度均为5.

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题