题目描述

现在有一个字符串s，需要求出s中最长回文子序列的长度。

回文串：顺读和倒读都一样的字符串

子序列：指一个字符串删掉部分字符（也可以不删）形成的字符串。

输入格式

输入一个不带空格的字符串，并且字符串只包含小写字母，($4\leq 字符串长度 \leq 2000$)

输出格式

输出最长回文子序列的长度

样例数据

cbagcgeb

5

解释：子序列有很多，但最长的回文子序列只有bgcgb，所以答案为5