504 - 最长回文子序列(LPS)

回文是正序与逆序相同的非空字符串。

例如civicracecar都是回文子串。任意单个字符的回文是其本身。

已知一个字符串S(只包含小写字母),求这个字符串的最长回文子序列的长度。

输入

输入一行只包含小写字母的字符串S

输出

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

样例

输入

bbbab

输出

4

输入

abcdba

输出

5

输入

jmcoding

输出

1

提示

数据规模

|S| <= 1000,字符串S只包含小写字母

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